Rust

use std::collections::{BTreeSet, HashMap, HashSet};

use itertools::Itertools;

pub fn solve_part_1(input: &str) -> String {
    let board: Vec<Vec<_>> = input.lines().map(|l| l.chars().collect()).collect();
    let mut front: HashSet<_> = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == 'D')
        .collect();
    let mut visited = HashSet::new();
    let knight_moves: [(isize, isize); 8] = [
        (2, 1),
        (2, -1),
        (-2, -1),
        (-2, 1),
        (1, 2),
        (1, -2),
        (-1, -2),
        (-1, 2),
    ];
    for _ in 0..=4 {
        let mut next_front = HashSet::new();
        for (i, j) in front.drain() {
            for (di, dj) in knight_moves {
                let (ni, nj) = (i.wrapping_add_signed(di), j.wrapping_add_signed(dj));
                if ni >= board.len() || nj >= board[0].len() {
                    continue;
                }
                if visited.contains(&(ni, nj)) {
                    continue;
                }
                next_front.insert((ni, nj));
            }
            visited.insert((i, j));
        }
        front = next_front;
    }
    visited
        .drain()
        .filter(|&(i, j)| board[i][j] == 'S')
        .count()
        .to_string()
}

fn solve_part_2_with_turns(input: &str, turns: usize) -> String {
    let board: Vec<Vec<_>> = input.lines().map(|l| l.chars().collect()).collect();
    let mut front: HashSet<_> = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == 'D')
        .collect();
    let knight_moves: [(isize, isize); 8] = [
        (2, 1),
        (2, -1),
        (-2, -1),
        (-2, 1),
        (1, 2),
        (1, -2),
        (-1, -2),
        (-1, 2),
    ];
    let mut eaten_sheep = HashSet::new();
    for turn in 0..=turns {
        let mut next_front = HashSet::new();
        for (i, j) in front.drain() {
            for (di, dj) in knight_moves {
                let (ni, nj) = (i.wrapping_add_signed(di), j.wrapping_add_signed(dj));
                if ni >= board.len() || nj >= board[0].len() {
                    continue;
                }
                next_front.insert((ni, nj));
            }
            if board[i][j] != '#' {
                if let Some(sheep_i) = (i + 1).checked_sub(turn)
                    && board[sheep_i][j] == 'S'
                {
                    eaten_sheep.insert((sheep_i, j));
                }
                if let Some(sheep_i) = i.checked_sub(turn)
                    && turn != 0
                    && board[sheep_i][j] == 'S'
                {
                    eaten_sheep.insert((sheep_i, j));
                }
            }
        }
        front = next_front;
    }
    eaten_sheep.len().to_string()
}

pub fn solve_part_2(input: &str) -> String {
    solve_part_2_with_turns(input, 20)
}
type VeryComplexType = HashMap<(usize, usize, usize, Vec<(usize, usize)>), usize>;
fn count_winning_sequences(
    turn: usize,
    dragon: (usize, usize),
    hiding_places: &HashSet<(usize, usize)>,
    sheep: BTreeSet<(usize, usize)>,
    height: usize,
    width: usize,
    cache: &mut VeryComplexType,
) -> usize {
    if sheep.is_empty() {
        return 1;
    }
    let cache_key = (
        turn % 2,
        dragon.0,
        dragon.1,
        sheep.iter().cloned().collect(),
    );
    if let Some(result) = cache.get(&cache_key) {
        return *result;
    }
    if turn % 2 == 1 {
        let knight_moves: [(isize, isize); 8] = [
            (2, 1),
            (2, -1),
            (-2, -1),
            (-2, 1),
            (1, 2),
            (1, -2),
            (-1, -2),
            (-1, 2),
        ];
        let (i, j) = dragon;
        let mut total = 0;
        for (di, dj) in knight_moves {
            let (ni, nj) = (i.wrapping_add_signed(di), j.wrapping_add_signed(dj));
            if ni >= height || nj >= width {
                continue;
            }
            if !hiding_places.contains(&(ni, nj)) && sheep.contains(&(ni, nj)) {
                let mut new_sheep = sheep.clone();
                new_sheep.remove(&(ni, nj));
                total += count_winning_sequences(
                    turn + 1,
                    (ni, nj),
                    hiding_places,
                    new_sheep,
                    height,
                    width,
                    cache,
                );
            } else {
                total += count_winning_sequences(
                    turn + 1,
                    (ni, nj),
                    hiding_places,
                    sheep.clone(),
                    height,
                    width,
                    cache,
                );
            }
        }
        cache.insert(cache_key, total);
        total
    } else {
        let mut sheep_moves_available = false;
        let mut total = 0;
        for &(i, j) in sheep.iter() {
            if dragon == (i + 1, j) && !hiding_places.contains(&(i + 1, j)) {
                continue;
            }
            sheep_moves_available = true;
            if i == (height - 1) {
                continue;
            }
            let mut new_sheep = sheep.clone();
            new_sheep.remove(&(i, j));
            new_sheep.insert((i + 1, j));
            total += count_winning_sequences(
                turn + 1,
                dragon,
                hiding_places,
                new_sheep,
                height,
                width,
                cache,
            );
        }
        if !sheep_moves_available {
            return count_winning_sequences(
                turn + 1,
                dragon,
                hiding_places,
                sheep,
                height,
                width,
                cache,
            );
        }
        cache.insert(cache_key, total);
        total
    }
}

pub fn solve_part_3(input: &str) -> String {
    let board: Vec<Vec<_>> = input.lines().map(|l| l.chars().collect()).collect();
    let dragon = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == 'D')
        .exactly_one()
        .unwrap();
    let sheep = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == 'S')
        .collect::<BTreeSet<_>>();
    let hiding_places = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == '#')
        .collect::<HashSet<_>>();
    let mut cache = HashMap::new();
    count_winning_sequences(
        0,
        dragon,
        &hiding_places,
        sheep,
        board.len(),
        board[0].len(),
        &mut cache,
    )
    .to_string()
}

Haskell

Hmm. I’m still not very happy with part 3: it’s a bit slow and messy. Doing state over the list monad for memoization doesn’t work well, so I’m enumerating all possible configurations first and taking advantage of laziness.

import Control.Monad  
import Data.Bifunctor  
import Data.Ix  
import Data.List  
import Data.Map (Map)  
import Data.Map qualified as Map  
import Data.Maybe  
import Data.Set.Monad (Set)  
import Data.Set.Monad qualified as Set  
import Data.Tuple  

type Pos = (Int, Int)  

readInput :: String -> ((Pos, Pos), Pos, Set Pos, Set Pos)  
readInput s =  
  let grid =  
        Map.fromList  
          [ ((i, j), c)  
            | (i, cs) <- zip [0 ..] $ lines s,  
              (j, c) <- zip [0 ..] cs  
          ]  
   in ( ((0, 0), fst $ Map.findMax grid),  
        fst $ fromJust $ find ((== 'D') . snd) $ Map.assocs grid,  
        Set.fromList $ Map.keys (Map.filter (== 'S') grid),  
        Set.fromList $ Map.keys (Map.filter (== '#') grid)  
      )  

moveDragon (i, j) = Set.mapMonotonic (bimap (+ i) (+ j)) offsets  
  where  
    offsets = Set.fromList ([id, swap] <*> ((,) <$> [-1, 1] <*> [-2, 2]))  

dragonMoves bounds =  
  iterate (Set.filter (inRange bounds) . (>>= moveDragon)) . Set.singleton  

part1 n (bounds, start, sheep, _) =  
  (!! n)  
    . map (Set.size . Set.intersection sheep)  
    . scanl1 Set.union  
    $ dragonMoves bounds start  

part2 n (bounds, dragonStart, sheepStart, hideouts) =  
  (!! n)  
    . map ((Set.size sheepStart -) . Set.size)  
    . scanl'  
      ( \sheep eaten ->  
          (Set.\\ eaten)  
            . Set.mapMonotonic (first (+ 1))  
            . (Set.\\ eaten)  
            $ sheep  
      )  
      sheepStart  
    . map (Set.\\ hideouts)  
    $ (tail $ dragonMoves bounds dragonStart)  

part3 (bounds, dragonStart, sheepStart, hideouts) =  
  count (dragonStart, sheepStart)  
  where  
    sheepStartByColumn = Map.fromList $ map swap $ Set.elems sheepStart  
    sheepConfigs =  
      map  
        ( (Set.fromList . catMaybes)  
            . zipWith (\j -> fmap (,j)) (Map.keys sheepStartByColumn)  
        )  
        . mapM  
          ( ((Nothing :) . map Just)  
              . (`enumFromTo` (fst $ snd bounds))  
          )  
        $ Map.elems sheepStartByColumn  
    count =  
      ((Map.!) . Map.fromList . map ((,) <*> go))  
        ((,) <$> range bounds <*> sheepConfigs)  
    go (dragon, sheep)  
      | null sheep = 1  
      | otherwise =  
          (sum . map count) $ do  
            let movableSheep =  
                  filter (\(_, p) -> p /= dragon || Set.member p hideouts) $  
                    map (\(i, j) -> ((i, j), (i + 1, j))) $  
                      Set.elems sheep  
                sheepMoves =  
                  if null movableSheep  
                    then [sheep]  
                    else do  
                      (p1, p2) <- movableSheep  
                      return $ Set.insert p2 $ Set.delete p1 sheep  
            sheep' <- sheepMoves  
            guard $ all (inRange bounds) sheep'  
            dragon' <- Set.elems $ moveDragon dragon  
            guard $ inRange bounds dragon'  
            let eaten = Set.singleton dragon' Set.\\ hideouts  
            return (dragon', sheep' Set.\\ eaten)  

main = do  
  readFile "everybody_codes_e2025_q10_p1.txt" >>= print . part1 4 . readInput  
  readFile "everybody_codes_e2025_q10_p2.txt" >>= print . part2 20 . readInput  
  readFile "everybody_codes_e2025_q10_p3.txt" >>= print . part3 . readInput