Rust

Like many it seems, this one also broke my brain. Its basically the same as Day 19, but something about it mentally broke me.

#[cfg(test)]
mod tests {
    use std::collections::HashMap;

    static NUMPAD: [[char; 3]; 4] = [
        ['7', '8', '9'],
        ['4', '5', '6'],
        ['1', '2', '3'],
        ['X', '0', 'A'],
    ];
    static DPAD: [[char; 3]; 2] = [['X', '^', 'A'], ['<', 'v', '>']];

    fn valid_path(pad: &[[char; 3]], start: (isize, isize), path: &str) -> bool {
        let mut pos = (start.0, start.1);
        for c in path.chars() {
            match c {
                '^' => pos.0 -= 1,
                'v' => pos.0 += 1,
                '<' => pos.1 -= 1,
                '>' => pos.1 += 1,
                'A' => {}
                _ => unreachable!(),
            };

            if pad[pos.0 as usize][pos.1 as usize] == 'X' {
                return false;
            }
        }
        true
    }

    fn move_pad(pad: &[[char; 3]], start: char, end: char) -> Vec<String> {
        let mut start_coord = (0, 0);
        let mut end_coord = (0, 0);
        for i in 0..pad.len() {
            for j in 0..3 {
                if pad[i][j] == end {
                    end_coord = (i as isize, j as isize);
                }
                if pad[i][j] == start {
                    start_coord = (i as isize, j as isize);
                }
            }
        }

        let delta_i = end_coord.0 - start_coord.0;
        let vert = match delta_i {
            -3 => "^^^",
            -2 => "^^",
            -1 => "^",
            0 => "",
            1 => "v",
            2 => "vv",
            3 => "vvv",
            _ => unreachable!(),
        };

        let delta_j = end_coord.1 - start_coord.1;
        let horz = match delta_j {
            -2 => "<<",
            -1 => "<",
            0 => "",
            1 => ">",
            2 => ">>",
            _ => unreachable!(),
        };

        let vert_path = horz.to_string() + vert + "A";
        let horz_path = vert.to_string() + horz + "A";

        if !valid_path(pad, start_coord, &vert_path) {
            return vec![horz_path];
        }
        if !valid_path(pad, start_coord, &horz_path) {
            return vec![vert_path];
        }
        vec![vert_path, horz_path]
    }

    fn dpad_seq_len(p0: &str, depth: usize, cache: &mut HashMap<(String, usize), usize>) -> usize {
        if depth == 0 {
            return p0.len();
        }
        if let Some(cost) = cache.get(&(p0.to_string(), depth)) {
            return *cost;
        }

        let mut first = 'A';
        let mut length = 0;
        for second in p0.chars() {
            let moves = move_pad(&DPAD, first, second);
            let mut min = usize::MAX;
            for m in moves {
                let l = dpad_seq_len(&m, depth - 1, cache);
                if l < min {
                    min = l;
                }
            }
            length += min;
            first = second;
        }
        cache.insert((p0.to_string(), depth), length);
        length
    }

    fn numpad_seq_len(
        p0: &str,
        depth: usize,
        cache: &mut HashMap<(String, usize), usize>,
    ) -> usize {
        let mut first = 'A';

        let mut length = 0;
        for second in p0.chars() {
            let moves = move_pad(&NUMPAD, first, second);
            let mut min = usize::MAX;
            for m in moves {
                let l = dpad_seq_len(&m, depth, cache);
                if l < min {
                    min = l;
                }
            }
            length += min;
            first = second;
        }

        length
    }

    #[test]
    fn test_numpad2dpad() {
        let mut cache = HashMap::new();
        assert_eq!(68, numpad_seq_len("029A", 2, &mut cache));
        assert_eq!(60, numpad_seq_len("980A", 2, &mut cache));
        assert_eq!(68, numpad_seq_len("179A", 2, &mut cache));
        assert_eq!(64, numpad_seq_len("456A", 2, &mut cache));
        assert_eq!(64, numpad_seq_len("379A", 2, &mut cache));
    }

    #[test]
    fn day21_part1_test() {
        let mut cache = HashMap::new();
        let input = std::fs::read_to_string("src/input/day_21.txt").unwrap();
        let codes = input.split('\n').collect::<Vec<&str>>();

        let mut total = 0;
        for code in codes {
            let min_length = numpad_seq_len(code, 2, &mut cache);
            println!("{code}: {min_length}");
            total += min_length * code[0..3].parse::<usize>().unwrap();
        }
        println!("{}", total);
    }

    #[test]
    fn day21_part2_test() {
        let mut cache = HashMap::new();
        let input = std::fs::read_to_string("src/input/day_21.txt").unwrap();
        let codes = input.split('\n').collect::<Vec<&str>>();

        let mut total = 0;
        for code in codes {
            let min_length = numpad_seq_len(code, 25, &mut cache);
            println!("{code}: {min_length}");
            total += min_length * code[0..3].parse::<usize>().unwrap();
        }
        println!("{}", total);
    }
}

Rust

For me this was the hardest puzzle so far this year. First I did a bunch of things that turned out not to work properly. For example I tried to solve it with a greedy algorithm that always moved horizontally first then vertically, but that ignores the gaps that need to be avoided (what a sneaky requirement) and also somehow doesn’t guarantee the shortest sequence.

After reaching part 2 it became clear that a recursive function (with memoization) is needed again, and of course in the end it turned out a lot simpler than what I had cooked up before (you don’t want to see that). Now even part 2 takes just 1.6ms.

use euclid::{default::*, point2, vec2};
use rustc_hash::FxHashMap;
use std::iter;

type Move = Option<Vector2D<i32>>;

const KEYPAD_GAP: Point2D<i32> = point2(0, 3);
const DPAD_GAP: Point2D<i32> = point2(0, 0);

fn keypad_pos(n: u8) -> Point2D<i32> {
    match n {
        b'7' => point2(0, 0),
        b'8' => point2(1, 0),
        b'9' => point2(2, 0),
        b'4' => point2(0, 1),
        b'5' => point2(1, 1),
        b'6' => point2(2, 1),
        b'1' => point2(0, 2),
        b'2' => point2(1, 2),
        b'3' => point2(2, 2),
        b'0' => point2(1, 3),
        b'A' => point2(2, 3),
        other => panic!("Invalid keypad symbol {other}"),
    }
}

// `None` is used for A
fn dpad_pos(d: Move) -> Point2D<i32> {
    match d {
        Some(Vector2D { x: 0, y: -1, .. }) => point2(1, 0),
        None => point2(2, 0),
        Some(Vector2D { x: -1, y: 0, .. }) => point2(0, 1),
        Some(Vector2D { x: 0, y: 1, .. }) => point2(1, 1),
        Some(Vector2D { x: 1, y: 0, .. }) => point2(2, 1),
        other => panic!("Invalid dpad symbol {other:?}"),
    }
}

fn moves_for_diff(diff: Vector2D<i32>, pos: Point2D<i32>, gap: Point2D<i32>) -> Vec<Vec<Move>> {
    let horizontal = iter::repeat_n(
        Some(vec2(diff.x.signum(), 0)),
        diff.x.unsigned_abs() as usize,
    );
    let vertical = iter::repeat_n(
        Some(vec2(0, diff.y.signum())),
        diff.y.unsigned_abs() as usize,
    );
    if pos + vec2(diff.x, 0) == gap {
        // Must not move horizontal first, or we hit the gap
        vec![vertical.chain(horizontal).chain(iter::once(None)).collect()]
    } else if pos + vec2(0, diff.y) == gap {
        vec![horizontal.chain(vertical).chain(iter::once(None)).collect()]
    } else {
        // Try both horizontal first and vertical first
        vec![
            horizontal
                .clone()
                .chain(vertical.clone())
                .chain(iter::once(None))
                .collect(),
            vertical.chain(horizontal).chain(iter::once(None)).collect(),
        ]
    }
}

fn dpad_sequence_len(
    start: Move,
    end: Move,
    rounds: u32,
    cache: &mut FxHashMap<(Move, Move, u32), u64>,
) -> u64 {
    if rounds == 0 {
        return 1;
    }
    if let Some(len) = cache.get(&(start, end, rounds)) {
        return *len;
    }
    let start_pos = dpad_pos(start);
    let end_pos = dpad_pos(end);
    let diff = end_pos - start_pos;
    let possible_paths = moves_for_diff(diff, start_pos, DPAD_GAP);
    let shortest_sequence = possible_paths
        .iter()
        .map(|moves| {
            moves
                .iter()
                .fold((0, None), |(cost, prev), &m| {
                    (cost + dpad_sequence_len(prev, m, rounds - 1, cache), m)
                })
                .0
        })
        .min()
        .unwrap();
    cache.insert((start, end, rounds), shortest_sequence);
    shortest_sequence
}

fn keypad_sequence_len(start: u8, end: u8, rounds: u32) -> u64 {
    let start_pos = keypad_pos(start);
    let end_pos = keypad_pos(end);
    let diff = end_pos - start_pos;
    let possible_paths = moves_for_diff(diff, start_pos, KEYPAD_GAP);
    let mut cache = FxHashMap::default();
    possible_paths
        .iter()
        .map(|moves| {
            moves
                .iter()
                .fold((0, None), |(cost, prev), &m| {
                    (cost + dpad_sequence_len(prev, m, rounds, &mut cache), m)
                })
                .0
        })
        .min()
        .unwrap()
}

fn solve(input: &str, rounds: u32) -> u64 {
    let mut sum: u64 = 0;
    for l in input.lines() {
        let mut prev = b'A';
        let mut len = 0;
        for b in l.bytes() {
            len += keypad_sequence_len(prev, b, rounds);
            prev = b;
        }
        let code_n: u64 = l.strip_suffix('A').unwrap().parse().unwrap();
        sum += code_n * len;
    }
    sum
}

fn part1(input: String) {
    println!("{}", solve(&input, 2));
}

fn part2(input: String) {
    println!("{}", solve(&input, 25));
}

util::aoc_main!();

Also on github

Dart

The secret ingredient is a big cache.

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

Map<String, Point<num>> mapper(List<String> list) => {
      for (var r in list.indexed())
        for (var c in r.value.split('').indexed())
          c.value: Point<num>(c.index, r.index)
    };
var dirMap = mapper(['_^A', '<v>']);
var numMap = mapper(['789', '456', '123', '_0A']);

var lenCache = <(String, int), int>{};
int len(String code, int level, isNum) =>
    lenCache.putIfAbsent((code, level), () => _len(code, level, isNum));
int n(p, isNum, level) => len(getMoves(p[0], p[1], isNum), level - 1, false);
int _len(String code, int level, isNum) => (level == 0)
    ? code.length
    : 'A$code'.split('').window(2).map((p) => n(p, isNum, level)).sum;

String getMoves(String f, String t, bool isNum) {
  var map = isNum ? numMap : dirMap;
  var (from, to) = (map[f]!, map[t]!);
  var mv = to - from;
  var s = <String>{};
  var x = ''.padRight(mv.x.abs() as int, mv.x.sign == 1 ? '>' : '<');
  var y = ''.padRight(mv.y.abs() as int, mv.y.sign == 1 ? 'v' : '^');
  // avoid '_', dislike '<'
  if (Point(from.x, to.y) != map['_']!) s.add('$y${x}A');
  if (Point(to.x, from.y) != map['_']!) s.add('$x${y}A');
  return (s.length < 2 || mv.x > 0) ? s.first : s.last;
}

int solve(String code, int level) =>
    len(code, level + 1, true) * int.parse(code.skipLast(1));

part1(List<String> lines) => lines.map((e) => solve(e, 2)).sum;
part2(List<String> lines) => lines.map((e) => solve(e, 25)).sum;

Haskell

I get the feeling this solution is more complicated than necessary, which means I probably haven’t understood the problem properly. Anyway, dynamic programming saves the day again!

import Control.Monad
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map

type Pos = (Int, Int)

makeKeypad :: [[Char]] -> Map Char Pos
makeKeypad rows = Map.fromList [(c, (i, j)) | (i, r) <- zip [0 ..] rows, (j, c) <- zip [0 ..] r, c /= '_']

numericKeypad = makeKeypad ["789", "456", "123", "_0A"]

directionalKeypad = makeKeypad ["_^A", "<v>"]

movesToButton :: Map Char Pos -> Pos -> Pos -> [[Char]]
movesToButton keypad (i1, j1) (i2, j2) =
  let di = i2 - i1
      dj = j2 - j1
      v = replicate (abs di) $ if di > 0 then 'v' else '^'
      h = replicate (abs dj) $ if dj > 0 then '>' else '<'
      hv = guard ((i1, j2) `elem` keypad) >> return (h ++ v)
      vh = guard ((i2, j1) `elem` keypad) >> return (v ++ h)
   in (++ ['A']) <$> nub (hv ++ vh)

indirectLength :: Int -> [Char] -> Int
indirectLength levels = (minimum . map (go levels)) . inputMoves numericKeypad
  where
    mapInput keypad f = (zipWith f <*> drop 1) . map (keypad Map.!) . ('A' :)
    inputMoves keypad = fmap concat . sequence . mapInput keypad (movesToButton keypad)
    go 0 = length
    go l = sum . mapInput directionalKeypad (\p1 p2 -> lengths Map.! (l, p1, p2))
    lengths =
      let ps = Map.elems directionalKeypad
       in Map.fromList [((l, p1, p2), bestLength l p1 p2) | l <- [1 .. levels], p1 <- ps, p2 <- ps]
    bestLength l p1 p2 =
      minimum . map (go (l - 1)) $ movesToButton directionalKeypad p1 p2

complexity :: Int -> String -> Int
complexity bots code = indirectLength bots code * read (init code)

main = do
  input <- lines <$> readFile "input21"
  mapM_ (print . sum . flip map input . complexity) [2, 25]