Finally got this one done very late last night!

I kept getting stuck reasoning about the recursion here. For some reason I got myself convinced that after a move, the state of the ‘upper’ dpads could make it more advantageous to pick one followup move over another - i.e. steps aren’t independent.

It took a bunch of manually working through sequences to convince myself that, after every move, every dpad above it would be on A. With that, it’s ‘just’ recursive pathfinding for independent moves.

Since there are relatively few types of moves needed on the dpad, I just sketched them out and wrote the routes in code directly (up to two options per move, e.g. left,up or up,left).

#include "common.h"

static int64_t dpmem[26][8][2];

enum {NW,NN,NE,EE,SE,SS,SW,WW};

/*
 * We can sufficiently describe npad/dpad movements as: "move N x, N y,
 * then press A N times" (a 'move'). It's never faster to take a detour.
 * After pressing A on one dpad, dpads on all levels above will also be
 * on A, so these moves can be considered in isolation.
 *
 * This function gives the cost of executing a move with the dpad in
 * direction 'd' at level 'l', excluding the A presses for actually
 * tapping the selected directions, but including returning the cursor
 * back to the A button.
 *
 * E.g., moving 2 up and 3 left (NW), the steps could be <AAv<AAA>>^.
 * Excluding the A presses, that's 6 steps. Pulling out the A presses
 * lets us drop the dx and dy arguments and simplify the memoization.
 * They're easily calculated: it's |dx|+|dy|.
 *
 * The gaps present a problem: picking the lowest-cost option (e.g.
 * left-then-up vs. up-then-left) may cause us to cross a gap. The
 * "mind the gap" argument 'mtg' must be set to 1 if-and-only-if there
 * is such potential, e.g. a move from < to ^ on the dpad (up,right
 * crosses the gap) or a move from A to 1 on the npad (left,up crosses
 * the gap). With the flag set, these orderings will be avoided.
 */
static int64_t
dp(int d, int mtg, int l)
{
	int64_t ret, alt=INT64_MAX;

	if (l<=0)
		return 0;
	
	assert(l >= 0);
	assert(l < (int)LEN(dpmem));
	assert(mtg==0 || mtg==1);

	if ((ret = dpmem[l][d][mtg]))
		return ret;

	/* routes avoiding gaps where necessary */
	ret = d==SE ? 1+dp(SS,0,l-1) + 1+dp(WW,0,l-1) + 2+dp(SE,0,l-1) :
	      d==SW ? 2+dp(SW,0,l-1) + 1+dp(WW,0,l-1) + 3+dp(NE,1,l-1) :
	      d==SS ? 2+dp(SW,0,l-1) + 2+dp(NE,0,l-1) :
	      d==NE ? 1+dp(SS,0,l-1) + 2+dp(NW,0,l-1) + 1+dp(EE,0,l-1) :
	      d==NW ? 1+dp(WW,0,l-1) + 2+dp(SW,1,l-1) + 3+dp(NE,1,l-1) :
	      d==NN ? 1+dp(WW,0,l-1) + 1+dp(EE,0,l-1) :
	      d==EE ? 1+dp(SS,0,l-1) + 1+dp(NN,0,l-1) :
	      d==WW ? 3+dp(SW,1,l-1) + 3+dp(NE,1,l-1) :
	      (assert(!"bad dir"), -1);

	/* alternatives crossing the gaps */
	alt = mtg ? INT64_MAX :
	      d==SE ? 2+dp(SW,0,l-1) + 1+dp(EE,0,l-1) + 1+dp(NN,0,l-1) :
	      d==SW ? 3+dp(SW,1,l-1) + 1+dp(EE,0,l-1) + 2+dp(NE,0,l-1) :
	      d==NE ? 1+dp(WW,0,l-1) + 2+dp(SE,0,l-1) + 1+dp(NN,0,l-1) :
	      d==NW ? 3+dp(SW,1,l-1) + 2+dp(NE,1,l-1) + 1+dp(EE,0,l-1) :
	      INT64_MAX;

	return dpmem[l][d][mtg] = MIN(ret, alt);
}

static int64_t
npcost(const char *s, int lv)
{
	int64_t cost=0;
	int x=2,y=3, x1,y1, mtg, dir;

	for (; *s == 'A' || (*s >= '0' && *s <= '9'); s++) {
		x1 = *s=='A' ? 2 : *s=='0' ? 1 : 2-(9-*s+'0') % 3;
		y1 = *s=='A' ? 3 : *s=='0' ? 3 :   (9-*s+'0') / 3;

		/* potentially crossing a gap? */
		mtg = (x==0 && y1==3) || (x1==0 && y==3);

		dir = y1>y ? (x1>x ? SE : x1<x ? SW : SS) :
		      y1<y ? (x1>x ? NE : x1<x ? NW : NN) :
		             (x1>x ? EE : x1<x ? WW : 0);

		cost += dp(dir, mtg, lv) + abs(x1-x) + abs(y1-y) +1;

		x = x1;
		y = y1;
	}

	return cost;
}

int
main(int argc, char **argv)
{
	char buf[8];
	int digits;
	int64_t p1=0,p2=0;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (fgets(buf, sizeof(buf), stdin)) {
		digits = atoi(buf);
		p1 += digits * npcost(buf, 2);
		p2 += digits * npcost(buf, 25);
	}

	printf("21: %"PRId64" %"PRId64"\n", p1, p2);
	return 0;
}

https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day21.c

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);
    }
}

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]

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;