Python

Took me quite a while to figure out. Did part 3 using DFS initially, then optimized to use memoization.

# queue for BFS
from collections import deque

# possible moves for the dragon (knight-like moves)
DRAGON_MOVES = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]

# yields all possible moves for dragon at (i, j)
def get_next_moves(i, j, m, n):
    for dx, dy in DRAGON_MOVES:
        n_i, n_j = i + dx, j + dy
        if 0 <= n_i < m and 0 <= n_j < n:
            yield n_i, n_j

# BFS for given number of moves
def part1(data: str, moves: int = 4):
    board = [list(row) for row in data.splitlines()]
    m, n = len(board), len(board[0])

    # initialize queue to dragon position
    queue = deque()
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'D':
                queue.append((i, j))

    eaten = 0
    visited = set()
    # perform BFS for the given number of moves
    # we do moves+1 because we only process a move after popping from queue
    for _ in range(moves+1):
        nq = len(queue)
        for _ in range(nq):
            i, j = queue.popleft()
            if (i, j) in visited:
                continue
            visited.add((i, j))

            # eat sheep if present
            if board[i][j] == 'S':
                eaten += 1

            # add unvisited next moves to queue
            for n_i, n_j in get_next_moves(i, j, m, n):
                if (n_i, n_j) in visited:
                    continue
                queue.append((n_i, n_j))

    return eaten

# <assert snipped>

def part2(data: str, rounds: int = 20):
    board = [list(row) for row in data.splitlines()]
    m, n = len(board), len(board[0])

    # initialize list to initial dragon location
    dragon_locs = []
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'D':
                dragon_locs.append((i, j))

    eaten = 0
    # simulate for given rounds
    for _ in range(rounds):
        # move dragon
        # calculate all possible new positions for the dragon
        dragon_moved_to = set()
        for i, j in dragon_locs:
            for n_i, n_j in get_next_moves(i, j, m, n):
                dragon_moved_to.add((n_i, n_j))
        # update dragon locations and eat any sheep present
        dragon_locs = list(dragon_moved_to)
        for i, j in dragon_locs:
            if board[i][j] == 'S':
                eaten += 1
                board[i][j] = '.'  # sheep is eaten

        # move sheep
        # process from bottom to top to avoid overlaps
        for i in range(m-1, -1, -1):
            for j in range(n):
                if 'S' not in board[i][j]:
                    # no sheep here
                    continue
                # move sheep out of current position
                board[i][j] = board[i][j].replace('S', '')
                if i == m-1:
                    # sheep escapes
                    continue
                if board[i+1][j] == '#':
                    # sheep moves into hiding
                    board[i+1][j] = 'S#'
                    continue
                if (i+1, j) in dragon_moved_to:
                    # sheep runs into dragon
                    eaten += 1
                    continue
                # sheep moves down
                board[i+1][j] = 'S'
            
    return eaten

# <assert snipped>

# DP with memoization
def part3(data: str):
    board_lines = data.splitlines()
    m, n = len(board_lines), len(board_lines[0])
    
    hideouts = set()            # positions of hideouts
    initial_sheep = [None] * n  # initial positions of sheep in each column
    dragon_loc = None           # initial position of dragon
    
    # iterate through board to find hideouts, sheep, and dragon
    for i in range(m):
        for j in range(n):
            char = board_lines[i][j]
            if char == '#':
                hideouts.add((i, j))
            elif char == 'D':
                dragon_loc = (i, j)
            elif char == 'S':
                initial_sheep[j] = i
    
    # convert to tuple for immutability and hashability
    initial_sheep = tuple(initial_sheep)

    # optional: calculate lost positions for each column
    # lost_positions[j] is the row index where if the sheep reaches, can escape or stay hidden until escape (game over)
    # used to quickly prune unwinnable states
    lost_positions = [m] * n
    for j in range(n):
        for i in range(m-1, -1, -1):
            if (i, j) not in hideouts:
                break
            lost_positions[j] = i

    # memoization of state to number of paths
    # state is a tuple of (player, dragon_loc, sheep_positions)
    memo = {}

    # do sheeps' turn
    def solve_sheep(dragon_loc: tuple[int, int], sheep_positions: tuple[int|None, ...]) -> int:
        # check for memoized result
        state = ('S', dragon_loc, sheep_positions)
        if state in memo:
            return memo[state]
        
        total_paths = 0
        # used to check if any sheep can move
        # this helps determine if the dragon gets another turn
        can_move = False
        
        for j, i in enumerate(sheep_positions):
            if i is None:
                # no sheep in this column
                continue
            
            next_i = i + 1
            
            # Check collision with dragon
            if (next_i, j) == dragon_loc and (next_i, j) not in hideouts:
                # smart sheep avoids dragon
                continue
            
            # Check escape (entering safe zone)
            if next_i == lost_positions[j]:
                # this is a valid move, but its game over so we skip exploring further
                can_move = True
                continue
            
            # this sheep will move down
            can_move = True
            # create new state with sheep moved down
            new_sheep = list(sheep_positions)
            new_sheep[j] = next_i

            # continue solving for dragon's turn
            total_paths += solve_dragon(dragon_loc, tuple(new_sheep))
        
        # if no sheep could move, dragon gets another turn
        if not can_move:
            total_paths += solve_dragon(dragon_loc, sheep_positions)
        
        # memoize result before returning
        memo[state] = total_paths
        return total_paths

    # do dragon's turn
    def solve_dragon(dragon_loc, sheep_positions):
        # check for memoized result
        state = ('D', dragon_loc, sheep_positions)
        if state in memo:
            return memo[state]
        
        total_paths = 0
        i, j = dragon_loc
        
        # try all possible dragon moves
        for n_i, n_j in get_next_moves(i, j, m, n):
            # get where the sheep is in the column the dragon is moving to
            sheep_loc_in_col = sheep_positions[n_j]
            
            # if sheep is in the same row as the dragon and not in hideout, eat it
            if sheep_loc_in_col == n_i and (n_i, n_j) not in hideouts:
                sheep_count = sum(1 for x in sheep_positions if x is not None)
                if sheep_count == 1:
                    # all sheep eaten, end of path
                    total_paths += 1
                else:
                    # create new state with sheep eaten
                    new_sheep = list(sheep_positions)
                    new_sheep[n_j] = None
                    # continue solving for sheep's turn
                    total_paths += solve_sheep((n_i, n_j), tuple(new_sheep))
            else:
                # Empty, hideout, or sheep hidden in hideout
                # continue solving for sheep's turn with dragon moved
                total_paths += solve_sheep((n_i, n_j), sheep_positions)

        # memoize result before returning
        memo[state] = total_paths
        return total_paths

    # start solving with sheep's turn
    return solve_sheep(dragon_loc, initial_sheep)

# <asserts snipped>

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  

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