Even after 20 years in "nicer", "safer", "more modern" languages ... I still miss Lisp. It's the only language that makes me feel like I'm sculpting in clay, instead of carving stone (Haskell) or laying bricks (Java) or building with Lego (Python). Sure, sometimes the clay comes out kind of lumpy, but that's part of the experience.

(ql:quickload :str)
(ql:quickload :cl-ppcre)

(defun parse-names-line (line)
  (str:split "," line))

(defun parse-rule-line (line)
  (ppcre:register-groups-bind
      (initial finals)
      ("^([A-Za-z]) > ([A-Za-z,]+)$" line)
    (cons (char initial 0)
          (mapcar #'(lambda (s) (char s 0)) (str:split "," finals)))))

(defun read-inputs (filename)
  (let ((input-lines (uiop:read-file-lines filename)))
    (list (cons :names (parse-names-line (car input-lines)))
          (cons :rules (mapcar #'parse-rule-line (cddr input-lines))))))

(defun valid? (rules name)
  (flet ((valid-pair? (x y)
           (member y (cdr (assoc x rules)))))
    (loop for i from 0 to (- (length name) 2)
          when (not (valid-pair? (char name i) (char name (1+ i))))
            return nil
          finally (return t))))

(defun main-1 (filename)
  (let* ((names-and-rules (read-inputs filename))
         (names (cdr (assoc :names names-and-rules)))
         (rules (cdr (assoc :rules names-and-rules))))
    (loop for name in names
          when (valid? rules name)
            return name)))

(defun main-2 (filename)
  (let* ((names-and-rules (read-inputs filename))
         (names (cdr (assoc :names names-and-rules)))
         (rules (cdr (assoc :rules names-and-rules))))
    (loop for i from 0 to (1- (length names))
          sum (if (valid? rules (nth i names)) (1+ i) 0))))

(defun augment (rules prefixes)
  (flet ((augment-one (prefix)
           (mapcar #'(lambda (c) (str:concat prefix (string c)))
                   (cdr (assoc (uiop:last-char prefix) rules)))))
    (mapcan #'augment-one prefixes)))

(defun main-3 (filename)
  (let* ((min-length 7)
         (max-length 11)
         (names-and-rules (read-inputs filename))
         (rules (cdr (assoc :rules names-and-rules)))
         (prefixes (remove-if-not #'(lambda (prefix) (valid? rules prefix))
                                  (cdr (assoc :names names-and-rules))))
         (names-by-length (make-hash-table)))
    (loop for l from (apply #'min (mapcar #'length prefixes)) to max-length
          do (setf (gethash l names-by-length)
                   (remove-duplicates
                    (append (remove-if-not #'(lambda (prefix) (= l (length prefix))) prefixes)
                            (augment rules (gethash (1- l) names-by-length)))
                    :test #'equal)))
    (loop for l from min-length to max-length
          sum (length (gethash l names-by-length)))))

Python

# pairwise helps picking consecutive values easier
#   [A,B,C,D] -> [AB, BC, CD]
from itertools import pairwise

# returns names and dict[str, set[str]] of allowed transitions
def parse_data(data: str):
    transition_map = {}
    lines = data.splitlines()

    for rule_str in lines[2:]:
        before, after = rule_str.split(" > ")
        transition_map[before] = set(after.split(','))

    names = lines[0].split(',')
    return names, transition_map

# checks if name is valid according to transition_map
def is_name_valid(transition_map: dict[str, set[str]], name: str) -> bool:
    for a, b in pairwise(name):
        if a not in transition_map or b not in transition_map[a]:
            return False
    return True


def part1(data: str):
    names, transition_map = parse_data(data)
    for name in names:
        if is_name_valid(transition_map, name):
            return name

# <assert snipped>

def part2(data: str):
    ans = 0
    names, transition_map = parse_data(data)
    for i, name in enumerate(names):
        if is_name_valid(transition_map, name):
            ans += i + 1
    return ans

# <assert snipped>

def part3(data: str):
    prefixes, transition_map = parse_data(data)

    # remove prefixes that are sub-prefixes of others
    #   to avoid double counting
    superset_prefixes = []
    for i, p1 in enumerate(prefixes):
        for j, p2 in enumerate(prefixes):
            if i != j and p1.startswith(p2):
                break
        else:
            # no break -> p1 is not a sub-prefix
            superset_prefixes.append(p1)

    variants = 0
    for prefix in superset_prefixes:
        if not is_name_valid(transition_map, prefix):
            continue
        
        # DFS to count all valid name extensions
        stack = [(prefix[-1], len(prefix))]
        while stack:
            prev, name_len = stack.pop()
            if name_len >= 7:
                variants += 1
            if name_len == 11:
                continue

            for next_letter in transition_map.get(prev, []):
                stack.append((next_letter, name_len + 1))
        
    return variants

# <assert snipped>

Nim

Part 3 is a recursive solution with caching (memoization).

proc isValid(name: string, rules: Table[char, set[char]]): bool =
  for i in 0 ..< name.high:
    if name[i+1] notin rules[name[i]]: return false
  true

proc allNames(prefix: string, rules: Table[char, set[char]], range: Slice[int]): int =
  var memo {.global.}: Table[(int, char), int]
  if prefix.len >= range.b: return
  if (prefix.len, prefix[^1]) in memo: return memo[(prefix.len, prefix[^1])]

  for ch in rules.getOrDefault(prefix[^1]):
    if prefix.len + 1 >= range.a:
      inc result
    result += allNames(prefix & ch, rules, range)

  memo[(prefix.len, prefix[^1])] = result

proc solve_part1*(input: string): Solution =
  let (names, rules) = parseInput(input)
  for name in names:
    if name.isValid(rules):
      return Solution(kind: skString, strVal: name)

proc solve_part2*(input: string): Solution =
  let (names, rules) = parseInput(input)
  for ni, name in names:
    if name.isValid(rules):
      result.intVal += ni + 1

proc solve_part3*(input: string): Solution =
  let (names, rules) = parseInput(input)
  var seen: seq[string]
  for name in names:
    if not name.isValid(rules): continue
    if seen.anyIt(name.startsWith it): continue
    result.intVal += allNames(name, rules, 7..11)
    seen.add name

Full solution at Codeberg: solution.nim

Rust

Technically you don't need to store the names in part 3, but I was too lazy.

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

pub fn solve_part_1(input: &str) -> String {
    let (names, rules) = input.split_once("\n\n").unwrap();
    let names: Vec<&str> = names.split(",").collect();
    let rules: HashMap<char, HashSet<char>> = rules
        .lines()
        .map(|line| {
            let (from, to) = line.split_once(" > ").unwrap();
            let to = to.split(",");
            (
                from.chars().next().unwrap(),
                to.map(|s| s.chars().next().unwrap()).collect(),
            )
        })
        .collect();
    for name in names {
        let mut allowed_chars = rules.get(&name.chars().next().unwrap());
        let mut acceptable = true;
        for ch in name.chars().skip(1) {
            match allowed_chars {
                Some(allowed) => {
                    if !allowed.contains(&ch) {
                        acceptable = false;
                        break;
                    }
                    allowed_chars = rules.get(&ch);
                }
                None => {
                    panic!("no rules for letter {ch} in name {name}");
                }
            }
        }
        if acceptable {
            return name.to_string();
        }
    }
    panic!("all names bad");
}

pub fn solve_part_2(input: &str) -> String {
    let (names, rules) = input.split_once("\n\n").unwrap();
    let names: Vec<&str> = names.split(",").collect();
    let rules: HashMap<char, HashSet<char>> = rules
        .lines()
        .map(|line| {
            let (from, to) = line.split_once(" > ").unwrap();
            let to = to.split(",");
            (
                from.chars().next().unwrap(),
                to.map(|s| s.chars().next().unwrap()).collect(),
            )
        })
        .collect();
    let mut sum_of_indices = 0;
    for (i, name) in names.into_iter().enumerate() {
        let mut allowed_chars = rules.get(&name.chars().next().unwrap());
        let mut acceptable = true;
        for ch in name.chars().skip(1) {
            match allowed_chars {
                Some(allowed) => {
                    if !allowed.contains(&ch) {
                        acceptable = false;
                        break;
                    }
                    allowed_chars = rules.get(&ch);
                }
                None => {
                    panic!("no rules for letter {ch} in name {name}");
                }
            }
        }
        if acceptable {
            sum_of_indices += 1 + i;
        }
    }
    sum_of_indices.to_string()
}

fn gen_names_with_prefix(
    prefix: &str,
    rules: &HashMap<char, HashSet<char>>,
    result: &mut HashSet<String>,
) {
    if prefix.len() >= 7 {
        result.insert(prefix.to_string());
    }
    if prefix.len() == 11 {
        return;
    }
    let last_char = prefix.chars().last().unwrap();
    if let Some(next_chars) = rules.get(&last_char) {
        for next_char in next_chars {
            let new_prefix = format!("{prefix}{next_char}");
            gen_names_with_prefix(new_prefix.as_str(), rules, result);
        }
    }
}

pub fn solve_part_3(input: &str) -> String {
    let (prefix, rules) = input.split_once("\n\n").unwrap();
    let prefixes: Vec<_> = prefix.split(",").collect();
    let rules: HashMap<char, HashSet<char>> = rules
        .lines()
        .map(|line| {
            let (from, to) = line.split_once(" > ").unwrap();
            let to = to.split(",");
            (
                from.chars().next().unwrap(),
                to.map(|s| s.chars().next().unwrap()).collect(),
            )
        })
        .collect();
    let mut results: HashSet<String> = HashSet::new();
    prefixes
        .into_iter()
        .filter(|&name| {
            let mut allowed_chars = rules.get(&name.chars().next().unwrap());
            let mut acceptable = true;
            for ch in name.chars().skip(1) {
                match allowed_chars {
                    Some(allowed) => {
                        if !allowed.contains(&ch) {
                            acceptable = false;
                            break;
                        }
                        allowed_chars = rules.get(&ch);
                    }
                    None => {
                        panic!("no rules for letter {ch} in name {name}");
                    }
                }
            }
            acceptable
        })
        .for_each(|prefix| gen_names_with_prefix(prefix, &rules, &mut results));
    results.len().to_string()
}

Uiua

There's probably a good solution hiding in here, but this ain't it. I originally went for the combinatoric approach for part 3, but it was giving me an answer that turned out to be out by 8, so brute force came to the rescue.

Prep ← (
  ⊜□⊸≠@\n
  Pairs ← ≡⊂⊓(¤|⊜∘⊸≠@,)∩°□°⊟
  ⊃(≡(□Pairs⊜□⊸(¬⦷" > ")°□)↘1|⊜□⊸≠@,°□⊢)
  ↘¯1∧(⊂°□) ⊙["  "]
)
"Oronris,Urakris,Oroneth,Uraketh\nr > a,i,o\ni > p,w\nn > e,r\no > n,m\nk > f,r\na > k\nU > r\ne > t\nO > r\nt > h\n"
°□⊢▽⊸≡(/↧∊⊙(⧈₂∘°□))¤Prep # Part1 --> "Oroneth"
"Xanverax,Khargyth,Nexzeth,Helther,Braerex,Tirgryph,Kharverax\nr > v,e,a,g,y\na > e,v,x,r\ne > r,x,v,t\nh > a,e,v\ng > r,y\ny > p,t\ni > v,r\nK > h\nv > e\nB > r\nt > h\nN > e\np > h\nH > e\nl > t\nz > e\nX > a\nn > v\nx > z\nT > i\n"
/++1⊚≡(/↧∊⊙(⧈₂∘°□))¤Prep # Part2 --> 23
P ← Prep"Khara,Xaryt,Noxer,Kharax\nr > v,e,a,g,y\na > e,v,x,r,g\ne > r,x,v,t\nh > a,e,v\ng > r,y\ny > p,t\ni > v,r\nK > h\nv > e\nB > r\nt > h\nN > e\np > h\nH > e\nl > t\nz > e\nX > a\nn > v\nx > z\nT > i\n"
Keys  ← ⊙◌P
Names ← ◌ P
GoodNames ← (
  ˜▽Names≡(/↧∊⊙(⧈₂∘°□))¤P                 # Remove names that fail part2
  ▽⊸(¬≡(/+≡(⨬(0|≍∩⌞↙↧◡∩⧻∩°□)>◡∩(⧻°□))))⊸¤ # Exclude all names that are prefixes of others.
)
# Build up all names and count them. Yuk, slower, but righter.
⊙0GoodNames
≡◇([∘]
   ⍢(
    /◇⊂≡◇(□≡˜⊂⊙¤≡⊣▽⤚(=≡⊢)Keys⊸⊣) # Add next chars, collect.
    ⨬(∘|⊙+⟜⧻)⊸(≥7⧻⊢)             # Add to counts if long enough.
  | <11⊣△)
   ◌ # We don't need the data, just the counts.
)
/+

Scheme/Guile

You could probably build a (letter, length) => combination-count mapping pretty quickly for part 3, but dealing with overlap in the input elements seems like a pain if handled this way.

(import (rnrs io ports (6)))
#!curly-infix

(define (parse-file file-name) (let*
  ((lines (string-split (string-trim-both (call-with-input-file file-name get-string-all)) #\newline))
   (names (string-split (car lines) #\,))
   (rule-lines (cddr lines))
   (rules (map (lambda (l) (let*
                       ((sides (string-split l #\space))
                        (r-left (string-ref (car sides) 0))
                        (r-right (caddr sides)))
                       (cons r-left (map (lambda (x) (string-ref x 0)) (string-split r-right #\,))))) rule-lines)))
  (cons names rules)))

(define (check-name rules name)
  (if (eq? 1 (string-length name))
      #t
      (let* ((letter (string-ref name 0))
             (right (assq-ref rules letter))
             (next-letter (string-ref name 1)))
        (if (memq next-letter right)
            (check-name rules (substring/read-only name 1))
            #f))))
(let* ((parsed (parse-file "notes/everybody_codes_e2025_q07_p1.txt"))
       (names (car parsed))
       (rules (cdr parsed)))
  (let loop ((names names))
    (let* ((name (car names)) (name-matches (check-name rules name)))
      (if name-matches
          (format #t "P1 Answer: ~a\n\n" name)
          (loop (cdr names))))))


(let* ((parsed (parse-file "notes/everybody_codes_e2025_q07_p2.txt"))
       (names (car parsed))
       (rules (cdr parsed)))
  (let loop ((i 1) (names names) (name-sum 0))
    (if (null? names)
        (format #t "P2 Answer: ~a\n\n" name-sum)
        (let* ((name (car names)) (name-matches (check-name rules name)))
          (loop (1+ i) (cdr names) (+ name-sum (if name-matches i 0)))))))


(define discovered-prefixes (make-hash-table))
(define (count-prefixes rules name)
  (if (hash-ref discovered-prefixes name)
      0
      (begin
        (hash-set! discovered-prefixes name #t)
        (if {(string-length name) >= 11}
            1
            (+
              (apply + (map
                     (lambda (c) (count-prefixes rules (string-append name (string c))))
                     (or (assq-ref rules (string-ref name (1- (string-length name)))) '())))
              (if {(string-length name) >= 7} 1 0))))))
(let* ((parsed (parse-file "notes/everybody_codes_e2025_q07_p3.txt"))
       (names (car parsed))
       (rules (cdr parsed)))
  (let ((name-count (apply + (map (lambda (name) (count-prefixes rules name)) (filter (lambda (name) (check-name rules name)) names)))))
    (format #t "P3 Answer: ~a\n\n" name-count)))

Haskell

A nice dynamic programming problem in part 3.

import Data.List  
import Data.List.Split  
import Data.Map.Lazy qualified as Map  
import Data.Maybe  

readInput s =  
  let (names : _ : rules) = lines s  
   in (splitOn "," names, map readRule rules)  
  where  
    readRule s =  
      let [[c], post] = splitOn " > " s  
       in (c, map head $ splitOn "," post)  

validBy rules name = all (`check` name) rules  
  where  
    check (c, cs) = all (`elem` cs) . following c  
    following c s = [b | (a : b : _) <- tails s, a == c]  

part1 (names, rules) = fromJust $ find (validBy rules) names  

part2 (names, rules) =  
  sum $ map fst $ filter (validBy rules . snd) $ zip [1 ..] names  

part3 (names, rules) =  
  sum . map go . filter (validBy rules) $ dedup names  
  where  
    dedup xs =  
      filter (\x -> not $ any (\y -> x /= y && y `isPrefixOf` x) xs) xs  
    go n = count (length n) (last n)  
    gen 11 _ = 1  
    gen len c =  
      (if len >= 7 then (1 +) else id)  
        . maybe 0 (sum . map (count (len + 1)))  
        $ lookup c rules  
    count =  
      curry . (Map.!) . Map.fromList $  
        [ ((k, c), gen k c)  
          | k <- [1 .. 11],  
            c <- map fst rules ++ concatMap snd rules  
        ]  

main = do  
  readFile "everybody_codes_e2025_q07_p1.txt" >>= putStrLn . part1 . readInput  
  readFile "everybody_codes_e2025_q07_p2.txt" >>= print . part2 . readInput  
  readFile "everybody_codes_e2025_q07_p3.txt" >>= print . part3 . readInput