Advent of Rust 14 and 15: Bits And/Or Pieces

This blog: chronicling my adventure of teaching myself the Rust programming language since December 1, courtesy of the programming puzzles at Advent of Code 2020. I’m not sure if anyone is reading anymore at this point 😆

Day 14, Part 1

Today’s puzzle is once again simulating some computer instructions, although the model this time is simple enough that I don’t feel I have to write a struct with methods to simulate it.

We have to write values into memory addresses, with a bitmask: XX1100XX (left to right, most significant to least significant, which I’ll refer to as bit 7 through 0) means that bits 7 and 6 of the value to be written are left unchanged, bits 5 and 4 are overwritten with 0, bits 3 and 2 are overwritten with 1, and bits 1 and 0 are also left unchanged. The answer to the puzzle is the sum of all the values in memory.

Contrary to what people might expect about programmers, I have not memorized how to set a bit to 0 or 1 in a number, so I always look it up to make sure I’m doing it correctly, before I do it. To set a bit to 0, use the bitwise AND operator (& in most languages) with an integer consisting of all bits 1 except the bit you want to set to 0; and to set a bit to 1, use the bitwise OR operator (| in most languages) with the bit that you want to set to 1. Based on this, I decide to write a function to parse the bitmask string, and it will split the bitmask into two bitmasks: an AND-mask to set bits to 0, and an OR-mask to set them to 1. So in the example I gave above, the AND-mask would be 11110011 and the OR-mask would be 00110000.

To read the other lines in the file I’ll use my old friend scan_fmt!(). Finally, to emulate the memory, I’ll use a HashMap<u64, u64>. Naively emulating it in an array that spans the entire 2³⁶-word address space would be a bit big (288 GiB). I do quickly look up “rust sparse array” but don’t find anything that seems more compelling than a hash map.

While writing the program I do need to look up “rust exponentiation” and find that numbers have a pow() method. But I do get an error:

error[E0689]: can't call method `pow` on ambiguous numeric type `{integer}`
  --> puzzle14.rs:38:35
   |
38 |             b'0' => and_mask -= 2.pow(ix),
   |                                   ^^^
   |
help: you must specify a concrete type for this numeric value, like `i32`
   |
38 |             b'0' => and_mask -= 2_i32.pow(ix),
   |                                 ^^^^^

That syntax (2_i32) is new to me, I haven’t seen it (or seen it suggested by the compiler) before.

error[E0308]: mismatched types
  --> puzzle14.rs:38:43
   |
38 |             b'0' => and_mask -= 2_u64.pow(ix),
   |                                           ^^ expected `u32`, found `usize`
   |
help: you can convert an `usize` to `u32` and panic if the converted value wouldn't fit
   |
38 |             b'0' => and_mask -= 2_u64.pow(ix.try_into().unwrap()),
   |                                           ^^^^^^^^^^^^^^^^^^^^^^

This I’m also surprised at, why does u64::pow() take u32 specifically and not u64 or usize?

error[E0599]: no method named `try_into` found for type `usize` in the current scope
  --> puzzle14.rs:41:45
   |
41 |             b'1' => or_mask += 2_u64.pow(ix.try_into()?),
   |                                             ^^^^^^^^ method not found in `usize`
   |
   = help: items from traits can only be used if the trait is in scope
help: the following trait is implemented but not in scope; perhaps add a `use` for it:
   |
1  | use std::convert::TryInto;
   |

It would be nice if the compiler would suggest that when suggesting try_into() in the first place!

Otherwise, writing the solution to Part 1 goes smoothly:¹

use std::collections::HashMap;
use std::convert::TryInto;
use std::num;

#[macro_use]
extern crate scan_fmt;

fn main() -> Result<(), Box<dyn Error>> {
    let mut memory = HashMap::new();
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;

    let file = fs::File::open("input")?;
    for line in read_lines(file) {
        if line.starts_with("mask") {
            let (new_or_mask, new_and_mask) = parse_mask(&line[7..])?;
            or_mask = new_or_mask;
            and_mask = new_and_mask;
            continue;
        }
        let (addr, value) = scan_fmt!(&line, "mem[{}] = {}", u64, u64)?;
        memory.insert(addr, value & and_mask | or_mask);
    }

    println!("{}", memory.values().sum::<u64>());

    Ok(())
}

fn parse_mask(line: &str) -> Result<(u64, u64), num::TryFromIntError> {
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;

    for (ix, byte) in line.bytes().rev().enumerate() {
        match byte {
            b'0' => and_mask -= 2_u64.pow(ix.try_into()?),
            b'1' => or_mask += 2_u64.pow(ix.try_into()?),
            b'X' => (),
            _ => panic!("Bad byte {}", byte),
        }
    }
    Ok((or_mask, and_mask))
}

I’m slightly surprised at a few of these type annotations:

• memory has type HashMap<u64, u64>, so memory.values() has type Iterator<Item = u64>, so memory.values().sum() should unambiguously be u64?
• and_mask and or_mask have type u64, so if I add or subtract 2^ix then that could be assumed to be u64 as well?

Day 14, Part 2

In Part 2, the meaning of the bitmask changes. Now it applies to the address being written to, not the value being written. A zero in the mask now has no effect on the value, so we ignore the AND-mask; a one in the mask means the same thing as in Part 1, so we continue to use the OR-mask; and now the Xs mean that that bit in the mask is “floating”, meaning that we have to write the value to both of the memory addresses in which that bit is either 0 or 1. (And if we have two Xs in the mask, then we have to write to four memory addresses, etc.)

Nonetheless, the program can almost remain the same! First I change parse_mask() to return a third mask as well, the float_mask, which has 1s in the bits that are supposed to be floating:

fn parse_mask(line: &str) -> Result<(u64, u64, u64), num::TryFromIntError> {
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;
    let mut float_mask: u64 = 0;

    for (ix, byte) in line.bytes().rev().enumerate() {
        let bit = 2_u64.pow(ix.try_into()?);
        match byte {
            b'0' => and_mask -= bit,
            b'1' => or_mask += bit,
            b'X' => float_mask += bit,
            _ => panic!("Bad byte {}", byte),
        }
    }
    Ok((or_mask, and_mask, float_mask))
}

I change the memory.insert(addr, value & and_mask | or_mask); line to instead do write_floating_memory(&mut memory, addr | or_mask, value, float_mask); if we are in Part 2.

The write_floating_memory() function is a bit more involved. I do know that we have to write the value to 2ⁿ addresses, where n is the number of 1-bits in the float mask, so I know I can iterate through the values from 0 to 2ⁿ − 1 and use each bit of each of those values in place of one of the floating bits. But I struggle somewhat with getting those bits into the right place.

I try a few things and then I realize that I can use the iterated value as a vector of bits, where I can pop bits off the end after I’ve used them, with the right shift operator (>>). So that’s what I write:

fn write_floating_memory(memory: &mut HashMap<u64, u64>, addr: u64, value: u64, float_mask: u64) {
    for mut floating_bits in 0..2_u64.pow(float_mask.count_ones()) {
        let mut masked_addr = addr;
        for bit_ix in 0..36 {
            let bit = 2_u64.pow(bit_ix);
            if float_mask & bit != 0 {
                match floating_bits & 1 {
                    0 => masked_addr &= !bit,
                    1 => masked_addr |= bit,
                    _ => panic!("Not possible"),
                };
                floating_bits >>= 1;
            }
        }
        memory.insert(masked_addr, value);
    }
}

There’s probably a more efficient way to do that by using bit-manipulation operators, but doing that intuitively is not my strong suit, and I’d rather not have to think hard about it when I can just solve the puzzle this way.

I initially get the wrong answer from the example input because I forgot to ignore the AND-mask (I had addr & and_mask | or_mask.) While debugging this, I learn the {:b} and {:036b} formats for println!(), which are useful for printing out the masks.

Once that is solved, though, I get the right answer for the example input, and then for the real puzzle.

Instead of “Not possible” it seems like it would be useful to have bit pattern matching in the match expression. I’m not the only one to have suggested this and I find the bitmatch package, but I don’t bother changing anything at this point now that I’ve got the answer.

Day 15, Part 1

I happened to solve the Day 15 puzzle within about 20 minutes after it was released, so I’m tacking it on to today’s entry.

The puzzle is a counting game played by the elves at the North Pole. Each person takes a turn reading off a list of starting numbers, and once the starting numbers are done, the game begins. The next player considers whether the last player’s number had been spoken before. If not, they say 0. If so, they say the number of turns between the previous time the number was spoken, and the last turn number. The puzzle answer is the number that’s spoken on turn 2020.

A few considerations that I made when writing the program below:

• This time we don’t even have to read the input from a file, it’s given in the puzzle, so I delete read_lines() from the boilerplate.
• I originally think I have to store the last two occurrences of the given number, and shift them along when the number occurs again, but the last occurrence is actually always the previous turn. I only have to store the second-to-last occurrence, and insert the previous turn’s number after the calculation for this turn.
• I use 0-based turn numbers internally, but 1-based when printing them out. “Turn 2020” is a human-readable 1-based number, so it’s actually turn 2019 internally.
• The number spoken after the starting numbers are done is always 0, because the starting numbers each occur for the first time.

fn main() {
    let input = vec![15, 12, 0, 14, 3, 1];
    let mut last_seen: HashMap<u16, u16> = input
        .iter()
        .enumerate()
        .map(|(turn, starting_number)| (*starting_number, turn as u16))
        .collect();
    let mut last_turn_number = 0;

    for turn in (input.len() as u16 + 1)..2020 {
        let this_turn_number = match last_seen.get(&last_turn_number) {
            Some(prev_seen) => turn - 1 - prev_seen,
            None => 0,
        };
        last_seen.insert(last_turn_number, turn - 1);
        last_turn_number = this_turn_number;

        println!("Turn {}: {}", turn + 1, this_turn_number);
    }
}

Day 15, Part 2

The answer to Part 2 is the number that is spoken on turn 30 million. I figure this will take an inconvenient amount of time to calculate, but not so inconvenient that I don’t want to try a brute force solution. I change the types of the integers to usize everywhere, to accommodate the larger numbers, and add an if expression, and that’s it, really. It takes a few minutes to run, but it’s done.

fn main() {
    let input = vec![15, 12, 0, 14, 3, 1];
    let mut last_seen: HashMap<usize, usize> = input
        .iter()
        .enumerate()
        .map(|(turn, starting_number)| (*starting_number, turn))
        .collect();
    let mut last_turn_number = 0;

    for turn in (input.len() + 1)..if is_part2() { 30000000 } else { 2020 } {
        let this_turn_number = match last_seen.get(&last_turn_number) {
            Some(prev_seen) => turn - 1 - prev_seen,
            None => 0,
        };
        last_seen.insert(last_turn_number, turn - 1);
        last_turn_number = this_turn_number;

        println!("Turn {}: {}", turn + 1, this_turn_number);
    }
}

Afterword

After Day 14 I was going to say that it seems like the puzzles follow a general pattern of having Part 1 be a fairly straightforward problem, and Part 2 adding a complication that makes you have to think harder about it. But Day 15 breaks that mold!

---

[1] For certain definitions of “smoothly,” that is. I’ve gotten used to always having a few rounds of compilation where I fix the borrow operators, and any program that I post here should be understood to have been bashed into shape by the compiler — I still can’t write Rust ↩

Advertisement