Haskell

Not particularly optimized but good enough.

import Control.Arrow ((***))  
import Data.Array (assocs)  
import Data.Function (on)  
import Data.Graph  
import Data.List  
import Data.Map (Map)  
import Data.Map qualified as Map  
import Data.Maybe  

readInput :: String -> Map Int [Char]  
readInput = Map.fromList . map ((read *** tail) . break (== ':')) . lines  

findRelations :: Map Int [Char] -> Graph  
findRelations dna =  
  buildG (1, Map.size dna)  
    . concatMap (\(x, (y, z)) -> [(x, y), (x, z)])  
    . mapMaybe (\x -> (x,) <$> findParents x)  
    $ Map.keys dna  
  where  
    findParents x =  
      find (isChild x) $  
        [(y, z) | (y : zs) <- tails $ delete x $ Map.keys dna, z <- zs]  
    isChild x (y, z) =  
      all (\(a, b, c) -> a == b || a == c) $  
        zip3 (dna Map.! x) (dna Map.! y) (dna Map.! z)  

scores :: Map Int [Char] -> Graph -> [Int]  
scores dna relations =  
  [similarity x y * similarity x z | (x, [y, z]) <- assocs relations]  
  where  
    similarity i j =  
      length . filter (uncurry (==)) $ zip (dna Map.! i) (dna Map.! j)  

part1, part2, part3 :: Map Int [Char] -> Int  
part1 = sum . (scores <*> findRelations)  
part2 = part1  
part3 = sum . maximumBy (compare `on` length) . components . findRelations  

main = do  
  readFile "everybody_codes_e2025_q09_p1.txt" >>= print . part1 . readInput  
  readFile "everybody_codes_e2025_q09_p2.txt" >>= print . part2 . readInput  
  readFile "everybody_codes_e2025_q09_p3.txt" >>= print . part3 . readInput  

Nim

Very messy bruteforce.

I've had some problems with parsing in part 2 - I didn't account for double digit numbers before dna sequences and that caused my code to work on example, but silently fail only on the real input. I've figured it out after ~30 minutes with some external help.

Part 3 runs in 700ms - not great, but not too bad either.

proc similarity(a, b: string): int =
  for i, c in a:
    if c == b[i]: inc result

proc solve_part1*(input: string): Solution =
  var sim: seq[int]

  var dnaList: seq[string]
  for line in input.splitLines():
    dnaList.add line[2..^1]

  for i in 0 .. dnaList.high:
    for j in i+1 .. dnaList.high:
      let s = similarity(dnaList[i], dnaList[j])
      sim.add s

  sim.sort()
  result := sim[^2] * sim[^1]

proc parentTest(ch, p1, p2: string): bool =
  for i, c in ch:
    if (c != p1[i]) and (c != p2[i]): return false
  true

proc simTable(dnaList: seq[string]): seq[seq[int]] =
  result = newSeqWith(dnaList.len, newseq[int](dnaList.len))
  for i in 0 .. dnaList.high:
    for j in i+1 .. dnaList.high:
      let s = similarity(dnaList[i], dnaList[j])
      result[i][j] = s
      result[j][i] = s

proc solve_part2*(input: string): Solution =
  var dnaList: seq[string]
  for line in input.splitLines():
    dnaList.add line.split(':')[1]

  let sim = simTable(dnaList)
  var indices = toseq(0..dnaList.high)
  for i, childDna in dnaList:
    var indices = indices
    indices.del i

    block doTest:
      for k in 0 .. indices.high:
        for j in k+1 .. indices.high:
          let p1 = indices[k]
          let p2 = indices[j]
          if parentTest(childDna, dnaList[p1], dnaList[p2]):
            result.intVal += sim[i][p1] * sim[i][p2]
            break doTest

proc solve_part3*(input: string): Solution =
  var dnaList: seq[string]
  for line in input.splitLines():
    dnaList.add line.split(':')[1]

  var families: seq[set[int16]]
  var indices = toseq(0..dnaList.high)
  for ch, childDna in dnaList:
    var indices = indices
    indices.del ch

    block doTest:
      for k in 0 .. indices.high:
        for j in k+1 .. indices.high:
          let p1 = indices[k]
          let p2 = indices[j]
          if parentTest(childDna, dnaList[p1], dnaList[p2]):
            families.add {ch.int16, p1.int16, p2.int16}
            break doTest

  var combined: seq[set[int16]]
  while families.len > 0:
    combined.add families.pop()
    var i = 0
    while i <= families.high:
      if (combined[^1] * families[i]).len > 0:
        combined[^1] = combined[^1] + families[i]
        families.del i
        i = 0
      else: inc i

  let maxInd = combined.mapIt(it.len).maxIndex
  result := combined[maxInd].toseq.mapIt(it.int+1).sum()

Full solution at Codeberg: solution.nim

Scheme/Guile

I was stuck on part 3 for a while, for not taking account that a child scale that I'm evaluating may already be a parent scale in some group.

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

(define (parse-file file-name)
  (let* ((lines (string-split (string-trim-both (call-with-input-file file-name get-string-all)) #\newline))
         (split-lines (map (lambda (l) (string-split l #\:)) lines))
         (parsed-lines (map (lambda (l) (cons (string->number (car l)) (string->list (cadr l)))) split-lines)))
    parsed-lines))

(define (child-score child p1 p2 p1-sim p2-sim)
  (if (and-map null? (list child p1 p2))
      (* p1-sim p2-sim)
      (let ((matches-p1 (eq? (car child) (car p1)))
            (matches-p2 (eq? (car child) (car p2))))
        (cond
          ((not (or matches-p1 matches-p2)) #f)
          (else (child-score (cdr child) (cdr p1) (cdr p2) (+ p1-sim (if matches-p1 1 0)) (+ p2-sim (if matches-p2 1 0))))))))
(let ((dna-lines (parse-file "notes/everybody_codes_e2025_q09_p1.txt")))
  (format #t "P1 Answer: ~a\n\n" (or
    (child-score (cdar dna-lines) (cdadr dna-lines) (cdaddr dna-lines) 0 0)
    (child-score (cdadr dna-lines) (cdar dna-lines) (cdaddr dna-lines) 0 0)
    (child-score (cdaddr dna-lines) (cdadr dna-lines) (cdar dna-lines) 0 0))))


(let ((dna-lines (list->vector (parse-file "notes/everybody_codes_e2025_q09_p2.txt"))))
  (let loop ((child 0) (total-sim 0))
    (if {child < (vector-length dna-lines)}
        (loop (1+ child) (+ total-sim (let loop ((i 0))
          (cond
            ((eq? i child) (loop (1+ i)))
            ({i >= {(vector-length dna-lines) - 1}} 0)
            (else
              (or
                (let loop ((j (1+ i)))
                  (cond
                    ((eq? j child) (loop (1+ j)))
                    ({j >= (vector-length dna-lines)} #f)
                    (else (let ((res (child-score
                               (cdr (vector-ref dna-lines child))
                               (cdr (vector-ref dna-lines i))
                               (cdr (vector-ref dna-lines j)) 0 0)))
                      (or res (loop (1+ j)))))))
                (loop (1+ i))))))))
        (format #t "P2 Answer: ~a\n\n" total-sim))))


(define (init-id-to-group dna-lines)
  (let ((table (make-hash-table)))
    (let loop ((i 0))
      (if {i < (vector-length dna-lines)}
          (let ((id (car (vector-ref dna-lines i))))
            (hash-set! table id id)
            (loop (1+ i)))
          table))))
(define (init-group-to-ids dna-lines)
  (let ((table (make-hash-table)))
    (let loop ((i 0))
      (if {i < (vector-length dna-lines)}
          (let ((id (car (vector-ref dna-lines i))))
            (hash-set! table id (list id))
            (loop (1+ i)))
          table))))
(let ((dna-lines (list->vector (parse-file "notes/everybody_codes_e2025_q09_p3.txt"))))
  (let ((id-to-group (init-id-to-group dna-lines)) (group-to-ids (init-group-to-ids dna-lines)))
  (let child-loop ((child 0))
    (if {child < (vector-length dna-lines)}
      (let i-loop ((i 0))
        (cond
          ((eq? i child) (i-loop (1+ i)))
          ({i >= {(vector-length dna-lines) - 1}} (child-loop (1+ child)))
          (else
            (let j-loop ((j (1+ i)))
              (cond
                ((eq? j child) (j-loop (1+ j)))
                ({j >= (vector-length dna-lines)} (i-loop (1+ i)))
                (else (let* ((cl (vector-ref dna-lines child))
                             (pil (vector-ref dna-lines i))
                             (pjl (vector-ref dna-lines j))
                             (res (child-score (cdr cl) (cdr pil) (cdr pjl) 0 0)))
                  (if res
                      (let* ((i-group (hash-ref id-to-group (car pil)))
                             (j-group (hash-ref id-to-group (car pjl)))
                             (child-group (hash-ref id-to-group (car cl)))
                             (i-group-ids (hash-ref group-to-ids i-group))
                             (j-group-ids (hash-ref group-to-ids j-group))
                             (child-group-ids (hash-ref group-to-ids child-group))
                             (new-group-ids (delete-duplicates (append child-group-ids (or i-group-ids '()) (or j-group-ids '())))))
                        (map (lambda (id) (hash-set! id-to-group id child-group)) new-group-ids)
                        (hash-remove! group-to-ids i-group)
                        (hash-remove! group-to-ids j-group)
                        (hash-set! group-to-ids child-group new-group-ids)
                        (child-loop (1+ child)))
                      (j-loop (1+ j))))))))))
        (format #t "P3 Answer: ~a\n\n" (cdr (hash-fold
                (lambda (_ id-list prior)
                        (let ((group-size (length id-list))
                              (group-sum (apply + id-list)))
                          (if {group-size > (car prior)}
                              (cons group-size group-sum)
                              prior)))
                (cons 0 0)
                group-to-ids)))))))

Python

# returns parents of child if found, else None
def get_parents(dnas: list[list[str]], child: int):
    candidates = len(dnas)
    seq_len = len(dnas[0])

    for p1 in range(candidates):
        if p1 == child:
            continue
        for p2 in range(p1 + 1, candidates):
            if p2 == child:
                continue

            for idx in range(seq_len):
                if dnas[child][idx] not in [dnas[p1][idx], dnas[p2][idx]]:
                    # mismatch found
                    break
            else:
                # no-break => all matched
                return p1, p2
    return None

# yields all children with their parents from a collection of dnas
def yield_children(dnas: list[list[str]]):
    for child in range(len(dnas)):
        parents = get_parents(dnas, child)
        if parents is not None:
            yield child, parents


def part1(data: str):
    # parse input data into list of DNA sequences
    dnas = [list(dna.split(":")[1]) for dna in data.splitlines()]
    seq_len = len(dnas[0])

    child, parents = next(yield_children(dnas))
    similarities = [0, 0]
    for idx in range(seq_len):
        for pi in range(2):
            if dnas[child][idx] == dnas[parents[pi]][idx]:
                similarities[pi] += 1

    return similarities[0] * similarities[1]


assert (
    part1("""1:CAAGCGCTAAGTTCGCTGGATGTGTGCCCGCG
2:CTTGAATTGGGCCGTTTACCTGGTTTAACCAT
3:CTAGCGCTGAGCTGGCTGCCTGGTTGACCGCG""")
    == 414
)


def part2(data: str):
    # parse input data into list of DNA sequences
    dnas = [list(dna.split(":")[1]) for dna in data.splitlines()]
    seq_len = len(dnas[0])

    children_gen = yield_children(dnas)

    all_similarity = 0
    for child, parents in children_gen:
        similarities = [0, 0]
        for idx in range(seq_len):
            for pi in range(2):
                if dnas[child][idx] == dnas[parents[pi]][idx]:
                    similarities[pi] += 1
        all_similarity += similarities[0] * similarities[1]
    return all_similarity


assert (
    part2("""1:GCAGGCGAGTATGATACCCGGCTAGCCACCCC
2:TCTCGCGAGGATATTACTGGGCCAGACCCCCC
3:GGTGGAACATTCGAAAGTTGCATAGGGTGGTG
4:GCTCGCGAGTATATTACCGAACCAGCCCCTCA
5:GCAGCTTAGTATGACCGCCAAATCGCGACTCA
6:AGTGGAACCTTGGATAGTCTCATATAGCGGCA
7:GGCGTAATAATCGGATGCTGCAGAGGCTGCTG""")
    == 1245
)


# Disjoint Set Union (Union-Find) data structure
#   with path compression and union by rank
class DSU:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find(self, x):
        # path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX == rootY:
            return False

        # union by rank
        #   attach smaller rank tree under root of higher rank tree
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            # ranks are same, so make one as root and increment its rank by one
            self.parent[rootY] = rootX
            self.rank[rootX] += 1

        return True


def part3(data: str):
    # parse input data into list of DNA sequences
    dnas = [list(dna.split(":")[1]) for dna in data.splitlines()]
    candidates = len(dnas)

    dsu = DSU(candidates)
    children_gen = yield_children(dnas)

    # union children with their parents
    for child, (p1, p2) in children_gen:
        dsu.union(child, p1)
        dsu.union(child, p2)
    
    # record [size, scale_sum] for each group
    groups = {}
    for scale_idx in range(candidates):
        # find the group of the current candidate
        group = dsu.find(scale_idx)
        # update group's size and scale sum
        entry = groups.setdefault(group, [0, 0])
        entry[0] += 1
        entry[1] += scale_idx + 1
    
    # return the maximum scale sum among all groups
    return max(groups.values())[1]


assert (
    part3("""1:GCAGGCGAGTATGATACCCGGCTAGCCACCCC
2:TCTCGCGAGGATATTACTGGGCCAGACCCCCC
3:GGTGGAACATTCGAAAGTTGCATAGGGTGGTG
4:GCTCGCGAGTATATTACCGAACCAGCCCCTCA
5:GCAGCTTAGTATGACCGCCAAATCGCGACTCA
6:AGTGGAACCTTGGATAGTCTCATATAGCGGCA
7:GGCGTAATAATCGGATGCTGCAGAGGCTGCTG""")
) == 12

assert (
    part3("""1:GCAGGCGAGTATGATACCCGGCTAGCCACCCC
2:TCTCGCGAGGATATTACTGGGCCAGACCCCCC
3:GGTGGAACATTCGAAAGTTGCATAGGGTGGTG
4:GCTCGCGAGTATATTACCGAACCAGCCCCTCA
5:GCAGCTTAGTATGACCGCCAAATCGCGACTCA
6:AGTGGAACCTTGGATAGTCTCATATAGCGGCA
7:GGCGTAATAATCGGATGCTGCAGAGGCTGCTG
8:GGCGTAAAGTATGGATGCTGGCTAGGCACCCG""")
) == 36

Rust

use std::collections::HashMap;

use bit_set::BitSet;
use itertools::{Itertools, izip};

type BitSetBase = u32;

fn is_child(child: &str, parent1: &str, parent2: &str) -> bool {
    izip!(child.chars(), parent1.chars(), parent2.chars()).all(|(c, a, b)| c == a || c == b)
}

fn similarity(a: &str, b: &str) -> usize {
    izip!(a.chars(), b.chars()).filter(|(a, b)| a == b).count()
}

fn unequality_bitset(a: &str, b: &str) -> BitSet<BitSetBase> {
    izip!(a.chars(), b.chars())
        .enumerate()
        .filter_map(|(i, (a_ch, b_ch))| if a_ch == b_ch { None } else { Some(i) })
        .collect()
}

pub fn solve_part_1(input: &str) -> String {
    let dnas = input
        .lines()
        .map(|l| {
            let (_, dna) = l.split_once(":").unwrap();
            dna
        })
        .collect::<Vec<_>>();
    let (child, parenta, parentb) = if is_child(dnas[0], dnas[1], dnas[2]) {
        (dnas[0], dnas[1], dnas[2])
    } else if is_child(dnas[1], dnas[0], dnas[2]) {
        (dnas[1], dnas[0], dnas[2])
    } else {
        (dnas[2], dnas[0], dnas[1])
    };
    (similarity(child, parenta) * similarity(child, parentb)).to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let dnas = input
        .lines()
        .map(|l| {
            let (_, dna) = l.split_once(":").unwrap();
            dna
        })
        .collect::<Vec<_>>();
    let unequalities = dnas
        .iter()
        .enumerate()
        .cartesian_product(dnas.iter().enumerate())
        .map(|((a_id, a), (b_id, b))| ((a_id, b_id), unequality_bitset(a, b)))
        .collect::<HashMap<_, _>>();
    let mut total_similarities = 0;
    'outer: for (child_id, &child_string) in dnas.iter().enumerate() {
        for (parent_a_id, &parent_a_string) in dnas.iter().enumerate() {
            if parent_a_id == child_id {
                continue;
            }
            for (parent_b_id, &parent_b_string) in dnas.iter().enumerate() {
                if parent_b_id == child_id || parent_b_id == parent_a_id {
                    continue;
                }
                if unequalities[&(child_id, parent_a_id)]
                    .intersection(&unequalities[&(child_id, parent_b_id)])
                    .count()
                    == 0
                {
                    total_similarities += similarity(child_string, parent_a_string)
                        * similarity(child_string, parent_b_string);
                    continue 'outer;
                }
            }
        }
    }
    total_similarities.to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let dnas = input
        .lines()
        .map(|l| {
            let (_, dna) = l.split_once(":").unwrap();
            dna
        })
        .collect::<Vec<_>>();
    let unequalities = dnas
        .iter()
        .enumerate()
        .cartesian_product(dnas.iter().enumerate())
        .map(|((a_id, a), (b_id, b))| ((a_id, b_id), unequality_bitset(a, b)))
        .collect::<HashMap<_, _>>();
    let mut parents: HashMap<usize, (usize, usize)> = HashMap::new();
    'outer: for (child_id, _) in dnas.iter().enumerate() {
        for (parent_a_id, _) in dnas.iter().enumerate() {
            if parent_a_id == child_id {
                continue;
            }
            for (parent_b_id, _) in dnas.iter().enumerate() {
                if parent_b_id == child_id || parent_b_id == parent_a_id {
                    continue;
                }
                if unequalities[&(child_id, parent_a_id)]
                    .intersection(&unequalities[&(child_id, parent_b_id)])
                    .count()
                    == 0
                {
                    parents.insert(child_id, (parent_a_id, parent_b_id));
                    continue 'outer;
                }
            }
        }
    }
    let mut family_id = (0usize..dnas.len()).collect::<Vec<_>>();
    for (child, (parent_a, parent_b)) in parents.drain() {
        let destination_family_id = family_id[child];
        let merge_families = (family_id[parent_a], family_id[parent_b]);
        for candidate_family in family_id.iter_mut() {
            if *candidate_family == merge_families.0 || *candidate_family == merge_families.1 {
                *candidate_family = destination_family_id;
            }
        }
    }
    let families = family_id
        .iter()
        .enumerate()
        .map(|(member_idx, &family_idx)| (family_idx, member_idx))
        .into_group_map();
    families
        .values()
        .max_by_key(|f| f.len())
        .unwrap()
        .iter()
        .map(|member_id| member_id + 1)
        .sum::<usize>()
        .to_string()
}