Skip Navigation
Advent Of Code @programming.dev
CameronDev @programming.dev

⌨️ - 2024 DAY 21 SOLUTIONS -⌨️

Day 21: Keypad Conundrum

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

7 comments

  • 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]

  • 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;

  • 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.

    Also on github

  • 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.

     rust
        
#[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);
    }
}

  • 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).

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

7 comments