This is my notes about solving Advent of Code 2020 in Rust.

Day 1

• There was outage for the first 10 minutes so there were no leaderboard scores
• I solved this using 3 nested loops:

for i in 0..x.len() {
    for j in 0..i {
        for k in 0..j {
            if x[i] + x[j] + x[k] == 2020 {
                return x[i] * x[j] * x[k];
            }
        }
    }
}

• Afterwards learned about combinations function from itertools crate:

let v = x
    .iter()
    .cloned()
    .combinations(3)
    .filter(|it| it.iter().sum::<i64>() == 2020)
    .next()
    .unwrap();
return v[0] * v[1] * v[2]

• Using tuple_combinations from the same package looks even cleaner:

let res = x
    .iter()
    .cloned()
    .tuple_combinations()
    .find_map(|(a, b, c)| {
        if a + b + c == 2020 {
            Some(a * b * c)
        } else {
            None
        }
    })
    .unwrap();
return res

Day 2

• Solved in 5/9 minutes and got around 800th place overall

• Wasted some time figuring out how to index String-s in Rust. The syntax is pretty ugly:

let ch = parts[1].chars().nth(0).unwrap();

• Lost another minute or so with incorrect answers as missed 1-indexing of arrays
• Initially did some parsing using my split_string and parse_i64 functions:

let parts = split_string(line, " ");
let nums = split_string(&parts[0], "-");
let a = parse_i64(&nums[0]);
let b = parse_i64(&nums[1]);
let ch = parts[1].chars().nth(0).unwrap();
let pass = parts[2];

• Afterwards found some pretty slick serde_scan crate:

let (a, b, ch, pass): (usize, usize, char, String) =
    serde_scan::scan!("{}-{} {}: {}" <- line).unwrap();

Day 3

• Solved in 6:44/10:11 minutes and got at #1240/#953 in global leaderboard

• Screwed up several times while trying to skim the statement too fast:
  • Missed that starting point is (1, 3) and not (0, 0) - this probably doesn’t matter since the start is not at tree
  • Didn’t realize that the map is cyclical
  • Missed that we need to multiply all numbers instead of sum
• Regarding Rust itself - I don’t like the access pattern for strings, so maybe I should have a helper to quickly convert String to Vec<Char>:

pub fn to_vv_char(lines: &Vec<String>) -> Vec<Vec<char>> {
    lines.iter().map(|x| x.chars().collect()).collect()
}

Day 4

• Solved in 11:19/28:05 minutes and got at #1800/1091 in global leaderboard

• Didn’t really like the problem since it was pretty straightforward but required a lot of careful coding
• Maybe that’s an opportunity to learn how to do that more efficiently in Rust (e.g. use regexps)
• For first part missed that cid is optional
• Also wasted some time with incorrect parsing - didn’t take into account last block
• Surprisingly second part worked out of the box the first time I finished it
• Will check if I can simplify some of the code
• Found that Vec has method contains and splitting the string is probably faster than changing it to a vector, so ecl check could be written as following:

fn check_ecl(s: &String) -> bool {
    let opts = split_string(&"amb blu brn gry grn hzl oth".to_string(), " ");
    opts.contains(s)
}

• iterators have methd .all that could be used for simplification:

fn is_all_digits(s: &String) -> bool {
    s.chars().all(|c| c.is_numeric())
}

Day 5

• Solved in 7:07/8:54 minutes and got at #593/379 place. The best result so far!

• Was pretty straightforward problem - I feel that I didn’t really screwed up anywhere
• Initially I implemented the binary search as described, but later turned out you can just convert the input string to binary treating “BR” -> 1 and “FL” -> 0:

fn get_seat_id_bin(s: &String) -> i64 {
    let x: String = s
        .chars()
        .map(|c| match c {
            'B' | 'R' => '1',
            _ => '0',
        })
        .collect();
    isize::from_str_radix(&x, 2).unwrap() as i64
}

• Or using .replace instead:

fn get_seat_id_bin(s: &String) -> i64 {
    let x = s.replace("B", "1").replace("R", "1").replace("L", "0").replace("F", "0");
    isize::from_str_radix(&x, 2).unwrap() as i64
}

Day 6

• Solved in 6:31/8:59 and got at #1911/#839: was a little slow than people in part 1 but then got faster in part 2.

• The parsing was pretty similar to day 4 and I still was using awkward state based parsing which is slower to implement
• Would be interesting to switch to .split("\n\n") based parsing since this seems more effective
• Part 1 using this approach:

pub fn part1(data: &str) -> i64 {
    data.trim()
        .split("\n\n")
        .map(|x| x.replace("\n", ""))
        .map(|x| {
            let set: HashSet<_> = x.chars().collect();
            set.len() as i64
        })
        .sum()
}

• Interestingly, Rust now only has .fold(value, func) which accumulates results into initial value. There is .fold_first(func) method in nightly that is more similar to traditional reduce (it uses the first value as initial).
• There is alo discussion on rust-lang API for supporting multiple sets
• Without that writing part 2 is a little awkward:

pub fn part2(data: &str) -> i64 {
    data.trim()
        .split("\n\n")
        .map(|x| x.split("\n"))
        .map(|lines| {
            let sets: Vec<_> = lines
                .map(|x| {
                    let set: HashSet<_> = x.chars().collect();
                    set
                })
                .collect();
            sets.iter()
                .fold(sets[0].clone(), |acc, s| {
                    acc.intersection(&s).copied().collect()
                })
                .len() as i64
        })
        .sum()
}

Day 7

• Solved in 21:27/30:08 and got at #1305/#1006.

• Spent some time trying to make fancy serde_scan work, but didn’t succeed and swtiched back to regular parsing/splitting
• Solved part 1 using BFS and part 2 using DFS with caching
• Learned cool API in Rust to populate HashMap<_, Vec<_>>. In C++ this is easy because of default ctor-s, but in Rust the convenient way to use the following:

g.entry(input_bag.clone())
    .or_insert(Vec::new())
    .push((num, output_bag.clone()));

• Parsing could also be re-written using regex crate:

let re = Regex::new("(.*) contain (.*)[.]").unwrap();
let cap = re.captures(line).unwrap();
let src = cap.get(1).unwrap().as_str();
let dsts = cap.get(2).unwrap().as_str();

Day 8

• Solved in 10:40/16:47 and got at #2519/#1144.

• Pretty slow overall as I spent debugging a few bugs in code:
  • Missed ip increment on regular instructions
  • Overflow of jump backwards instruction
• Learned that using pattern matching can make the program nicer:

fn run_prog(prog: &Vec<Op>) -> (bool, i64) {
    let mut acc = 0;
    let mut ip = 0;
    let mut visited = HashMap::new();
    loop {
        if ip as usize >= prog.len() {
            return (true, acc);
        }
        let key = ip;
        if visited.contains_key(&key) {
            return (false, acc);
        }
        visited.insert(key, true);
        let p = &prog[ip as usize];
        match p.name.as_str() {
            "acc" => {
                acc += p.value;
                ip += 1;
            }
            "jmp" => {
                ip = (ip + p.value).max(0);
            }
            _ => {
                ip += 1;
            }
        }
    }
}

Day 9

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
  9   00:07:27  1224      0   00:13:01   887      0

• Pretty easy day again. Mostly fighting my own typos / mistakes.
• Learned a few cool things though.
• Rust has convenient lambdas defined inline that could capture values from outside:

let is_valid = |x, start, end| {
    for i in start..end {
        for j in start..i {
            if v[i] + v[j] == x {
                return true;
            }
        }
    }
    return false;
};

• Rust ranges work on vectors:

let s: i64 = v[i..=j].iter().sum();
let min = v[i..=j].iter().min().unwrap();
let max = v[i..=j].iter().max().unwrap();

Day 10

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
 10   00:06:01   559      0   00:14:10   358      0

• Did pretty good - was pretty straightforward dynamic programming and worked almost from the first run

Day 11

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
 11   00:13:00   374      0   00:17:56   209      0

• Did pretty well - this is the best day so far.
• Solved Part 2 with 8 (!) nested scopes
• Later learned that rust allows overloading of any methods from existing struct. Here is how I was implementing .get and .set methods for vector based on a Vector2d (which is basically (x, y) pair):

pub trait GridExt {
    fn get(&self, v: Vector2d) -> char;
    fn set(&mut self, v: Vector2d, c: char);
}

impl GridExt for Vec<Vec<char>> {
    fn get(&self, v: Vector2d) -> char {
        self[v.y as usize][v.x as usize]
    }
    fn set(&mut self, v: Vector2d, c: char) {
        self[v.y as usize][v.x as usize] = c;
    }
}

Day 12

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
 12   00:10:22   871      0   00:15:54   356      0

• Had decent part 1, but then speed up at part 2 and gained 500 ranks.
• Learned that match is pretty convenient to use in Rust. You can also skip brackets { ... } if there just single expression inside match arm.

for (d, v) in actions {
    match d {
        'N' => wpt.y += v,
        'S' => wpt.y -= v,
        'E' => wpt.x += v,
        'W' => wpt.x -= v,
        'L' => {
            for i in 0..v / 90 {
                wpt = wpt.rotate_left();
            }
        }
        'R' => {
            for i in 0..v / 90 {
                wpt = wpt.rotate_right();
            }
        }
        'F' => pos = pos + wpt * v,
        _ => {}
    }
}

Day 13

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
 13   00:03:58    61     40   01:21:36  2161      0

• Did part 1 really was to even get into leaderboard, but then struggled with Part 2 as I forgot about Chineese Remainder Theorem (CRT)
• Some folks also solved it using sieving method that should be fast to implement.
• I essentially came up with inductive formula based on diophantine equation solver a * x + b * y = c
• However I also tried Rust’s big integers and found they are clunky as hell as require tons of .clone() calls all over the place. Worth checking if there are better alternatives.

Day 14

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
 14   00:18:35  1308      0   00:31:07   679      0

• Had a bug with bitwise operations in part 1 which caused timings quite slow

Day 15

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
 15   00:19:18  1952      0   00:38:07  2573      0

• Was solving part 1 with O(N^2) alogrithm and had many bugs in the process

Day 16

      -------Part 1--------   -------Part 2--------
Day       Time  Rank  Score       Time  Rank  Score
 16   00:16:36  1433      0   00:37:44   684      0

• Solved Part 1 in naive way by iterating through all columns and filling the match if there was only 1 possible one

Learned:

• .any() method on iterators in rust

let invalid = nums.iter().any(|x| is_outside_every(*x, &ranges));

• dbg!(..) to print values:

dbg!(tickets.len());
// [src/bin/day16.rs:98] tickets.len() = 191

Day 24

• Learned cool syntax for map update:

*tiles.entry(key).or_insert(0) += 1;

• Variables to functions could have mut modifier

fn walk(mut line: &str) -> (i64, i64) {
    while !line.is_empty() {
        line = line[1..]
    }
}

Final thoughts

• This year I continued using Rust. Now feeling more profficient - can probably solve most of the puzzles without looking into reference

Links

• Other Rust Solutions:
  • https://github.com/nulladdict/aoc-2020
  • https://github.com/floatdrop/aoc
  • https://github.com/smmalis37/aoc2020/
  • https://github.com/chinatsu/aoc2020
  • https://github.com/nwtnni/advent-of-code
• Vizualization of time taken for top-100:
  • http://www.maurits.vdschee.nl/scatterplot/
• Collection of many other related links:
  • https://github.com/Bogdanp/awesome-advent-of-code