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

  • @mykl@lemmy.world
    2•3 minutes ago

    Dart

    The secret ingredient is a big cache.

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

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

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;
  • lwhjp
    2•7 hours ago

    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]