undefined

    
: get-input ( -- rules updates )
  "vocab:aoc-2024/05/input.txt" utf8 file-lines
  { "" } split1
  "|" "," [ '[ [ _ split ] map ] ] bi@ bi* ;

: relevant-rules ( rules update -- rules' )
  '[ [ _ in? ] all? ] filter ;

: compliant? ( rules update -- ? )
  [ relevant-rules ] keep-under
  [ [ index* ] with map first2 < ] with all? ;

: middle-number ( update -- n )
  dup length 2 /i nth-of string>number ;

: part1 ( -- n )
  get-input
  [ compliant? ] with
  [ middle-number ] filter-map sum ;

: compare-pages ( rules page1 page2 -- <=> )
  [ 2array relevant-rules ] keep-under
  [ drop +eq+ ] [ first index zero? +gt+ +lt+ ? ] if-empty ;

: correct-update ( rules update -- update' )
  [ swapd compare-pages ] with sort-with ;

: part2 ( -- n )
  get-input dupd
  [ compliant? ] with reject
  [ correct-update middle-number ] with map-sum ;

  

 undefined

    
using QuickGraph;
using QuickGraph.Algorithms.TopologicalSort;
public class Day05 : Solver
{
  private List<int[]> updates;
  private List<int[]> updates_ordered;

  public void Presolve(string input) {
    var blocks = input.Trim().Split("\n\n");
    List<(int, int)> rules = new();
    foreach (var line in blocks[0].Split("\n")) {
      var pair = line.Split('|');
      rules.Add((int.Parse(pair[0]), int.Parse(pair[1])));
    }
    updates = new();
    updates_ordered = new();
    foreach (var line in input.Trim().Split("\n\n")[1].Split("\n")) {
      var update = line.Split(',').Select(int.Parse).ToArray();
      updates.Add(update);

      var graph = new AdjacencyGraph<int, Edge<int>>();
      graph.AddVertexRange(update);
      graph.AddEdgeRange(rules
        .Where(rule => update.Contains(rule.Item1) && update.Contains(rule.Item2))
        .Select(rule => new Edge<int>(rule.Item1, rule.Item2)));
      List<int> ordered_update = [];
      new TopologicalSortAlgorithm<int, Edge<int>>(graph).Compute(ordered_update);
      updates_ordered.Add(ordered_update.ToArray());
    }
  }

  public string SolveFirst() => updates.Zip(updates_ordered)
    .Where(unordered_ordered => unordered_ordered.First.SequenceEqual(unordered_ordered.Second))
    .Select(unordered_ordered => unordered_ordered.First)
    .Select(update => update[update.Length / 2])
    .Sum().ToString();

  public string SolveSecond() => updates.Zip(updates_ordered)
    .Where(unordered_ordered => !unordered_ordered.First.SequenceEqual(unordered_ordered.Second))
    .Select(unordered_ordered => unordered_ordered.Second)
    .Select(update => update[update.Length / 2])
    .Sum().ToString();
}

  

 undefined

    
fun part1(input: String): Int {
    val (rules, listOfNumbers) = parse(input)
    return listOfNumbers
        .filter { numbers -> numbers == sort(numbers, rules) }
        .sumOf { numbers -> numbers[numbers.size / 2] }
}

fun part2(input: String): Int {
    val (rules, listOfNumbers) = parse(input)
    return listOfNumbers
        .filterNot { numbers -> numbers == sort(numbers, rules) }
        .map { numbers -> sort(numbers, rules) }
        .sumOf { numbers -> numbers[numbers.size / 2] }
}

private fun sort(numbers: List<Int>, rules: List<Pair<Int, Int>>): List<Int> {
    return numbers.sortedWith { a, b -> if (rules.contains(a to b)) -1 else 1 }
}

private fun parse(input: String): Pair<List<Pair<Int, Int>>, List<List<Int>>> {
    val (rulesSection, numbersSection) = input.split("\n\n")
    val rules = rulesSection.lines()
        .mapNotNull { line -> """(\d{2})\|(\d{2})""".toRegex().matchEntire(line) }
        .map { match -> match.groups[1]?.value?.toInt()!! to match.groups[2]?.value?.toInt()!! }
    val numbers = numbersSection.lines().map { line -> line.split(',').map { it.toInt() } }
    return rules to numbers
}
  
  

 nim

    
proc parseRules(input: string): Table[int, seq[int]] =
  for line in input.splitLines():
    let pair = line.split('|')
    let (a, b) = (pair[0].parseInt, pair[1].parseInt)
    discard result.hasKeyOrPut(a, newSeq[int]())
    result[a].add b

proc solve(input: string): AOCSolution[int, int] =
  let chunks = input.split("\n\n")
  let later = parseRules(chunks[0])
  for line in chunks[1].splitLines():
    let numbers = line.split(',').map(parseInt)
    let sorted = numbers.sorted(cmp =
      proc(a,b: int): int =
        if a in later and b in later[a]: -1
        elif b in later and a in later[b]: 1
        else: 0
    )
    if numbers == sorted:
      result.part1 += numbers[numbers.len div 2]
    else:
      result.part2 += sorted[sorted.len div 2]


  

 undefined

    
import Control.Arrow
import Data.Bool
import Data.List
import Data.List.Split
import Data.Maybe

readInput :: String -> ([(Int, Int)], [[Int]])
readInput = (readRules *** readUpdates . tail) . break null . lines
  where
    readRules = map $ (read *** read . tail) . break (== '|')
    readUpdates = map $ map read . splitOn ","

mid = (!!) <*> ((`div` 2) . length)

isSortedBy rules = (`all` rules) . match
  where
    match ps (x, y) = fromMaybe True $ (<) <$> elemIndex x ps <*> elemIndex y ps

pageOrder rules = curry $ bool GT LT . (`elem` rules)

main = do
  (rules, updates) <- readInput <$> readFile "input05"
  let (part1, part2) = partition (isSortedBy rules) updates
  mapM_ (print . sum . map mid) [part1, sortBy (pageOrder rules) <$> part2]

  

 undefined

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

(int, int) solve(List<String> lines) {
  var parts = lines.splitAfter((e) => e == '');
  var pred = SetMultimap.fromEntries(parts.first.skipLast(1).map((e) {
    var ps = e.split('|').map(int.parse);
    return MapEntry(ps.last, ps.first);
  }));
  ordering(a, b) => pred[a].contains(b) ? 1 : 0;

  var pageSets = parts.last.map((e) => e.split(',').map(int.parse).toList());
  var partn = pageSets.partition((ps) => ps.isSorted(ordering));
  return (
    partn.truthy.map((e) => e[e.length ~/ 2]).sum,
    partn.falsey.map((e) => (e..sort(ordering))[e.length ~/ 2]).sum
  );
}

part1(List<String> lines) => solve(lines).$1;
part2(List<String> lines) => solve(lines).$2;


  

 undefined

    
Data ← ⊜(□)⊸≠@\n "47|53\n97|13\n97|61\n97|47\n75|29\n61|13\n75|53\n29|13\n97|29\n53|29\n61|53\n97|53\n61|29\n47|13\n75|47\n97|75\n47|61\n75|61\n47|29\n75|13\n53|13\n\n75,47,61,53,29\n97,61,53,29,13\n75,29,13\n75,97,47,61,53\n61,13,29\n97,13,75,29,47"
Rs   ← ≡◇(⊜⋕⊸≠@|)▽⊸≡◇(⧻⊚⌕@|)Data
Ps   ← ≡⍚(⊜⋕⊸≠@,)▽⊸≡◇(¬⧻⊚⌕@|)Data

NoPred  ← ⊢▽:⟜(≡(=0/+⌕)⊙¤)◴♭⟜≡⊣                # Find entry without predecessors.
GetLead ← ⊸(▽:⟜(≡(¬/+=))⊙¤)⟜NoPred             # Remove that leading entry.
Rules   ← ⇌⊂⊃(⇌⊢°□⊢|≡°□↘1)[□⍢(GetLead|≠1⧻)] Rs # Repeatedly find rule without predecessors (Kaaaaaahn!).

Sorted   ← ⊏⍏⊗,Rules
IsSorted ← /×>0≡/-◫2⊗°□: Rules
MidVal   ← ⊡:⟜(⌊÷ 2⧻)

⇌⊕□⊸≡IsSorted Ps        # Group by whether the pages are in sort order.
≡◇(/+≡◇(MidVal Sorted)) # Find midpoints and sum.


  

 undefined

    
   13 29 47 53 61 75 97
13  =  >  >  >  >  >  >
29  <  =  >  >  >  >  >
47  <  <  =  <  <  >  >
53  <  <  >  =  >  >  >
61  <  <  >  <  =  >  >
75  <  <  <  <  <  =  >
97  <  <  <  <  <  <  =


  

 haskell

    
import Control.Arrow hiding (first, second)

import Data.Map (Map)
import Data.Set (Set)
import Data.Bifunctor

import qualified Data.Maybe as Maybe
import qualified Data.List as List
import qualified Data.Map as Map
import qualified Data.Set as Set
import qualified Data.Ord as Ord


parseRule :: String -> (Int, Int)
parseRule s = (read . take 2 &&& read . drop 3) s

replace t r c = if t == c then r else c

parse :: String -> (Map Int (Set Int), [[Int]])
parse s = (map parseRule >>> buildRuleMap $ rules, map (map read . words) updates)
        where
                rules = takeWhile (/= "") . lines $ s
                updates = init . map (map (replace ',' ' ')) . drop 1 . dropWhile (/= "") . lines $ s

middleElement :: [a] -> a
middleElement us = (us !!) $ (length us `div` 2)

ruleGroup :: Eq a => (a, b) -> (a, b') -> Bool
ruleGroup = curry (uncurry (==) <<< fst *** fst)

buildRuleMap :: [(Int, Int)] -> Map Int (Set Int)
buildRuleMap rs = List.sortOn fst
        >>> List.groupBy ruleGroup 
        >>> map ((fst . head) &&& map snd) 
        >>> map (second Set.fromList) 
        >>> Map.fromList 
        $ rs

elementSort :: Map Int (Set Int) -> Int -> Int -> Ordering 
elementSort rs a b
        | Maybe.maybe False (Set.member b) (rs Map.!? a) = LT
        | Maybe.maybe False (Set.member a) (rs Map.!? b) = GT
        | otherwise = EQ

isOrdered rs u = (List.sortBy (elementSort rs) u) == u

part1 (rs, us) = filter (isOrdered rs)
        >>> map middleElement
        >>> sum
        $ us
part2 (rs, us) = filter (isOrdered rs >>> not)
        >>> map (List.sortBy (elementSort rs))
        >>> map middleElement
        >>> sum
        $ us

main = getContents >>= print . (part1 &&& part2) . parse

  

 haskell

    
import Control.Arrow
import Control.Monad
import Data.Char
import Data.List qualified as L
import Data.Map
import Data.Set
import Data.Set qualified as S
import Text.ParserCombinators.ReadP

parse = (,) <$> (fromListWith S.union <$> parseOrder) <*> (eol *> parseUpdate)
parseOrder = endBy (flip (,) <$> (S.singleton <$> parseInt <* char '|') <*> parseInt) eol
parseUpdate = endBy (sepBy parseInt (char ',')) eol
parseInt = read <$> munch1 isDigit
eol = char '\n'

verify :: Map Int (Set Int) -> [Int] -> Bool
verify m = and . (zipWith fn <*> scanl (flip S.insert) S.empty)
  where
    fn a = flip S.isSubsetOf (findWithDefault S.empty a m)

getMiddle = ap (!!) ((`div` 2) . length)

part1 m = sum . fmap getMiddle

getOrigin :: Map Int (Set Int) -> Set Int -> Int
getOrigin m l = head $ L.filter (S.disjoint l . preds) (S.toList l)
  where
    preds = flip (findWithDefault S.empty) m

order :: Map Int (Set Int) -> Set Int -> [Int]
order m s
  | S.null s = []
  | otherwise = h : order m (S.delete h s)
    where
      h = getOrigin m s

part2 m = sum . fmap (getMiddle . order m . S.fromList)

main = getContents >>= print . uncurry runParts . fst . last . readP_to_S parse
runParts m = L.partition (verify m) >>> (part1 m *** part2 m)

  

 nim

    
import ../aoc, strutils, sequtils, tables

type
  Rules = ref Table[int, seq[int]]

#check if an update sequence is valid
proc valid(update:seq[int], rules:Rules):bool =
  for pi, p in update:
    for r in rules.getOrDefault(p):
      let ri = update.find(r)
      if ri != -1 and ri < pi:
        return false
  return true

proc backtrack(p:int, index:int, update:seq[int], rules: Rules, sorted: var seq[int]):bool =
  if index == 0:
    sorted[index] = p
    return true
  
  for r in rules.getOrDefault(p):
    if r in update and r.backtrack(index-1, update, rules, sorted):
      sorted[index] = p
      return true
  
  return false

#fix an invalid sequence
proc fix(update:seq[int], rules: Rules):seq[int] =
  echo "fixing", update
  var sorted = newSeqWith(update.len, 0);
  for p in update:
    if p.backtrack(update.len-1, update, rules, sorted):
      return sorted
  return @[]

proc solve*(input:string): array[2,int] =
  let parts = input.split("\r\n\r\n");
  
  let rulePairs = parts[0].splitLines.mapIt(it.strip.split('|').map(parseInt))
  let updates = parts[1].splitLines.mapIt(it.split(',').map(parseInt))
  
  # fill rules table
  var rules = new Rules
  for rp in rulePairs:
    if rules.hasKey(rp[0]):
      rules[rp[0]].add rp[1];
    else:
      rules[rp[0]] = @[rp[1]]
      
  # fill reverse rules table
  var backRules = new Rules
  for rp in rulePairs:
    if backRules.hasKey(rp[1]):
      backRules[rp[1]].add rp[0];
    else:
      backRules[rp[1]] = @[rp[0]]
  
  for u in updates:
    if u.valid(rules):
      result[0] += u[u.len div 2]
    else:
      let uf = u.fix(backRules)
      result[1] += uf[uf.len div 2]

  

 haskell

    
import Data.Maybe as Maybe
import Data.List as List
import Control.Arrow hiding (first, second)

parseRule :: String -> (Int, Int)
parseRule s = (read . take 2 &&& read . drop 3) s

replace t r c = if t == c then r else c

parse :: String -> ([(Int, Int)], [[Int]])
parse s = (map parseRule rules, map (map read . words) updates)
        where
                rules = takeWhile (/= "") . lines $ s
                updates = init . map (map (replace ',' ' ')) . drop 1 . dropWhile (/= "") . lines $ s

validRule (pairLeft, pairRight) (ruleLeft, ruleRight)
        | pairLeft == ruleRight && pairRight == ruleLeft = False
        | otherwise = True

validatePair rs p = all (validRule p) rs

validateUpdate rs u = all (validatePair rs) pairs
        where 
                pairs = List.concatMap (\ t -> map (head t, ) (tail t)) . filter (length >>> (> 1)) . tails $ u

middleElement :: [a] -> a
middleElement us = (us !!) $ (length us `div` 2)

part1 (rs, us) = sum . map (middleElement) . filter (validateUpdate rs) $ us

insertOrderly rs i is = insertOrderly' frontRules i is
        where
                frontRules = filter (((== i) . fst)) rs

insertOrderly' _  i [] = [i]
insertOrderly' rs i (i':is)
        | any (snd >>> (== i')) rs = i : i' : is
        | otherwise = i' : insertOrderly' rs i is

part2 (rs, us) = sum . map middleElement . Maybe.mapMaybe ((orderUpdate &&& id) >>> \ p -> if (fst p /= snd p) then Just $ fst p else Nothing) $ us
        where
                orderUpdate = foldr (insertOrderly rs) []

main = getContents >>= print . (part1 &&& part2) . parse

  

 python

    
from functools import cmp_to_key
from pathlib import Path


def parse_input(input: str) -> tuple[dict[int, list[int]], list[list[int]]]:
    rules, updates = tuple(input.strip().split("\n\n")[:2])
    order = {}
    for entry in rules.splitlines():
        values = entry.split("|")
        order.setdefault(int(values[0]), []).append(int(values[1]))
    updates = [[int(v) for v in u.split(",")] for u in updates.splitlines()]
    return (order, updates)


def is_ordered(update: list[int], order: dict[int, list[int]]) -> bool:
    return update == sorted(
        update, key=cmp_to_key(lambda a, b: 1 if a in order.setdefault(b, []) else -1)
    )


def part_one(input: str) -> int:
    order, updates = parse_input(input)
    return sum([u[len(u) // 2] for u in (u for u in updates if is_ordered(u, order))])


def part_two(input: str) -> int:
    order, updates = parse_input(input)
    return sum(
        [
            sorted(u, key=cmp_to_key(lambda a, b: 1 if a in order[b] else -1))[
                len(u) // 2
            ]
            for u in (u for u in updates if not is_ordered(u, order))
        ]
    )


if __name__ == "__main__":
    input = Path("input").read_text("utf-8")
    print(part_one(input))
    print(part_two(input))

  

 undefined

    
from math import floor
from pathlib import Path
from functools import cmp_to_key
cwd = Path(__file__).parent

def parse_protocol(path):

  with path.open("r") as fp:
    data = fp.read().splitlines()

  rules = data[:data.index('')]
  page_to_rule = {r.split('|')[0]:[] for r in rules}
  [page_to_rule[r.split('|')[0]].append(r.split('|')[1]) for r in rules]

  updates = list(map(lambda x: x.split(','), data[data.index('')+1:]))

  return page_to_rule, updates

def sort_pages(pages, page_to_rule):

  compare_pages = lambda page1, page2:\
    0 if page1 not in page_to_rule or page2 not in page_to_rule[page1] else -1

  return sorted(pages, key = cmp_to_key(compare_pages))

def solve_problem(file_name, fix):

  page_to_rule, updates = parse_protocol(Path(cwd, file_name))

  to_print = [temp_p[int(floor(len(pages)/2))] for pages in updates
              if (not fix and (temp_p:=pages) == sort_pages(pages, page_to_rule))
              or (fix and (temp_p:=sort_pages(pages, page_to_rule)) != pages)]

  return sum(map(int,to_print))

  

 undefined

    
data_file_name =: '5.data'
lines =: cutopen fread data_file_name
NB. manuals start with the first line where the index of a comma is < 5
start_of_manuals =: 1 i.~ 5 > ',' i.~"1 > lines
NB. ". can't parse the | so replace it with a space
edges =: ". (' ' & (2}))"1 > start_of_manuals {. lines
NB. don't unbox and parse yet because they aren't all the same length
manuals =: start_of_manuals }. lines
max_page =: >./ , edges
NB. adjacency matrix of the page partial ordering; e.i. makes identity matrix
adjacency =: 1 (< edges)} e. i. >: max_page
NB. ordered line is true if line is ordered according to the adjacency matrix
ordered =: monad define
   pages =. ". > y
   NB. index pairs 0 <: i < j < n; box and raze to avoid array fill
   page_pairs =. ; (< @: (,~"0 i.)"0) i. # pages
   */ adjacency {~ <"1 pages {~ page_pairs
)
midpoint =: ({~ (<. @: -: @: #)) @: ". @: >
result1 =: +/ (ordered"0 * midpoint"0) manuals

NB. toposort line yields the pages of line topologically sorted by adjacency
NB. this is *not* a general topological sort but works for our restricted case:
NB. we know that each individual manual will be totally ordered
toposort =: monad define
   pages =. ". > y
   NB. for each page, count the pages which come after it, then sort descending
   pages \: +/"1 adjacency {~ <"1 pages ,"0/ pages
)
NB. midpoint2 doesn't parse, but does remove trailing zeroes
midpoint2 =: ({~ (<. @: -: @: #)) @: ({.~ (i. & 0))
result2 =: +/ (1 - ordered"0 manuals) * midpoint2"1 toposort"0 manuals

  

 undefined

    
import kotlin.text.Regex

fun main() {
    fun part1(input: List<String>): Int = parseInput(input).sumOf { if (it.isCorrectlyOrdered()) it[it.size / 2].pageNumber else 0 }

    fun part2(input: List<String>): Int = parseInput(input).sumOf { if (!it.isCorrectlyOrdered()) it.sorted()[it.size / 2].pageNumber else 0 }

    val testInput = readInput("Day05_test")
    check(part1(testInput) == 143)
    check(part2(testInput) == 123)

    val input = readInput("Day05")
    part1(input).println()
    part2(input).println()
}

fun parseInput(input: List<String>): List<List<Page>> {
    val (orderRulesStrings, pageSequencesStrings) = input.filter { it.isNotEmpty() }.partition { Regex("""\d+\|\d+""").matches(it) }

    val orderRules = orderRulesStrings.map { with(it.split('|')) { this[0].toInt() to this[1].toInt() } }
    val orderRulesX = orderRules.map { it.first }.toSet()
    val pages = orderRulesX.map { pageNumber ->
        val orderClasses = orderRules.filter { it.first == pageNumber }.map { it.second }
        Page(pageNumber, orderClasses)
    }.associateBy { it.pageNumber }

    val pageSequences = pageSequencesStrings.map { sequenceString ->
        sequenceString.split(',').map { pages[it.toInt()] ?: Page(it.toInt(), emptyList()) }
    }

    return pageSequences
}

/*
 * An order class is an equivalence class for every page with the same page to be printed before.
 */
data class Page(val pageNumber: Int, val orderClasses: List<Int>): Comparable<Page> {
    override fun compareTo(other: Page): Int =
        if (other.pageNumber in orderClasses) -1
        else if (pageNumber in other.orderClasses) 1
        else 0
}

fun List<Page>.isCorrectlyOrdered(): Boolean = this == this.sorted()

 
  

 smalltalk

    
day5p1: in
    | rules pages i j input |

    input := in lines.
    i := input indexOf: ''.
    rules := ((input copyFrom: 1 to: i-1) collect: [:l | (l splitOn: '|') collect: #asInteger]).
    pages := (input copyFrom: i+1 to: input size) collect: [:l | (l splitOn: ',') collect: #asInteger].
    
    ^ pages sum: [ :p |
        (rules allSatisfy: [ :rule |
            i := p indexOf: (rule at: 1).
            j := p indexOf: (rule at: 2).
            (i ~= 0 & (j ~= 0)) ifTrue: [ i < j ] ifFalse: [ true ]
        ])
            ifTrue: [p at: ((p size / 2) round: 0) ]
            ifFalse: [0].
    ]


  

 smalltalk

    
day5p2: in
    | rules pages i pnew input |

    input := in lines.
    i := input indexOf: ''.
    rules := ((input copyFrom: 1 to: i-1) collect: [:l | (l splitOn: '|') collect: #asInteger]).
    pages := (input copyFrom: i+1 to: input size) collect: [:l | (l splitOn: ',') collect: #asInteger].
    
    ^ pages sum: [ :p |
        pnew := p sorted: [ :x :y | 
            rules anySatisfy: [ :r | (r at: 1) = x and: [ (r at: 2) = y]]
        ].
        pnew ~= p
            ifTrue: [ pnew at: ((pnew size / 2) round: 0) ]
            ifFalse: [0].
    ]

  

 python

    
with open('input') as data:
    parts = data.read().rstrip().split("\n\n")
    ordering_rules = parts[0].split("\n")
    updates = parts[1].split("\n")

correct_updates = []
middle_updates = []

def find_relevant_rules(pg_num: str, rules: list[str]) -> list[str] | None:
    for rule in rules:
        return list(filter(lambda x: x.split("|")[0] == pg_num, rules))

def interpret_rule(rule: str) -> list[str]:
    return rule.split("|")

def interpret_update(update: str) -> list[str]:
    return update.split(",")

def find_middle_update_index(update: list[str]) -> int:
    num_of_elements = len(update)
    return num_of_elements // 2

for update in updates:
    is_correct = True
    for i, page in enumerate(interpret_update(update)):
       rules_to_check = find_relevant_rules(page, ordering_rules) 
       for rule in rules_to_check:
           if rule.split("|")[1] in interpret_update(update)[:i]:
               is_correct = False
    if is_correct:
        correct_updates.append(update)

for update in correct_updates:
    split_update = update.split(",")
    middle_updates.append(int(split_update[find_middle_update_index(split_update)]))
print(sum(middle_updates))

  

 uiua

    
FindNext ← ⊙(
  ⊡1⍉,
  ⊃▽(▽¬)⊸∈
  ⊙⊙(⊡0⍉.)
  :⊙(⟜(▽¬∈))
)

# find the order of pages for a given set of rules
FindOrder ← (
  ◴♭.
  []
  ⍢(⊂FindNext|⋅(>1⧻))
  ⊙◌⊂
)

PartOne ← (
  &rs ∞ &fo "input-5.txt"
  ∩°□°⊟⊜□¬⌕"\n\n".
  ⊙(⊜(□⊜⋕≠@,.)≠@\n.↘1)
  ⊜(⊜⋕≠@|.)≠@\n.

  ⊙.
  ¤
  ⊞(◡(°□:)
    ⟜:⊙(°⊟⍉)
    =2+∩∈
    ▽
    FindOrder
    ⊸≍°□:
    ⊙◌
  )
  ≡◇(⊡⌊÷2⧻.)▽♭
  /+
)

PartTwo ← (
  &rs ∞ &fo "input-5.txt"
  ∩°□°⊟⊜□¬⌕"\n\n".
  ⊙(⊜(□⊜⋕≠@,.)≠@\n.↘1)
  ⊜(⊜⋕≠@|.)≠@\n.
  ⊙.
  ⍜¤⊞(
    ◡(°□:)
    ⟜:⊙(°⊟⍉)
    =2+∩∈
    ▽
    FindOrder
    ⊸≍°□:
    ⊟∩□
  )
  ⊙◌
  ⊃(⊡0)(⊡1)⍉
  ≡◇(⊡⌊÷2⧻.)▽¬≡°□
  /+
)

&p "Day 5:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo

  

 csharp

    
// this is from a nuget package. My Mathy roommate told me this was a topological sort.
// It's also my preferred, since it'd perform better on larger data sets.
return lines
    .AsParallel()
    .Where(line => !IsInOrder(GetSoonestOccurrences(line), aggregateRules))
    .Sum(line => line.StableOrderTopologicallyBy(
            getDependencies: page =>
                aggregateRules.TryGetValue(page, out var mustPreceed) ? mustPreceed.Intersect(line) : Enumerable.Empty<Page>())
        .Middle()
    );

  

 csharp

    
public static SortedSet<Page> Sort3(Page[] line,
    Dictionary<Page, System.Collections.Generic.HashSet<Page>> rules)
{
    // how the hell is this working?
    var sorted = new SortedSet<Page>(new Sort3Comparer(rules));
    foreach (var page in line)
        sorted.Add(page);
    return sorted;
}

public static Page[] OrderBy(Page[] line, Dictionary<Page, System.Collections.Generic.HashSet<Page>> rules)
{
    return line.OrderBy(identity, new Sort3Comparer(rules)).ToArray();
}

sealed class Sort3Comparer : IComparer<Page>
{
    private readonly Dictionary<Page, System.Collections.Generic.HashSet<Page>> _rules;

    public Sort3Comparer(Dictionary<Page, System.Collections.Generic.HashSet<Page>> rules) => _rules = rules;

    public int Compare(Page x, Page y)
    {
        if (_rules.TryGetValue(x, out var xrules))
        {
            if (xrules.Contains(y))
                return -1;
        }

        if (_rules.TryGetValue(y, out var yrules))
        {
            if (yrules.Contains(x))
                return 1;
        }

        return 0;
    }
}

  

 undefined

    
use std::{
    cmp::Ordering,
    collections::HashMap,
    io::{BufRead, BufReader},
};

fn main() {
    let mut lines = BufReader::new(std::fs::File::open("input.txt").unwrap()).lines();

    let mut rules: HashMap<u64, Vec<u64>> = HashMap::default();

    for line in lines.by_ref() {
        let line = line.unwrap();

        if line.is_empty() {
            break;
        }

        let lr = line
            .split('|')
            .map(|el| el.parse::<u64>())
            .collect::<Result<Vec<u64>, _>>()
            .unwrap();

        let left = lr[0];
        let right = lr[1];

        if let Some(values) = rules.get_mut(&left) {
            values.push(right);
            values.sort();
        } else {
            rules.insert(left, vec![right]);
        }
    }

    let mut updates: Vec<Vec<u64>> = Vec::default();

    for line in lines {
        let line = line.unwrap();

        let update = line
            .split(',')
            .map(|el| el.parse::<u64>())
            .collect::<Result<Vec<u64>, _>>()
            .unwrap();

        updates.push(update);
    }

    let mut middle_sum = 0;
    let mut fixed_middle_sum = 0;

    for update in updates {
        let mut update_sorted = update.clone();
        update_sorted.sort_by(|a, b| {
            if let Some(rules) = rules.get(a) {
                if rules.contains(b) {
                    Ordering::Less
                } else {
                    Ordering::Equal
                }
            } else {
                Ordering::Equal
            }
        });

        if update.eq(&update_sorted) {
            let middle = update[(update.len() - 1) / 2];
            middle_sum += middle;
        } else {
            let middle = update_sorted[(update_sorted.len() - 1) / 2];
            fixed_middle_sum += middle;
        }
    }

    println!("part1: {} part2: {}", middle_sum, fixed_middle_sum);
}

  

 rust

    
use std::{cmp::Ordering, fs, str::FromStr};

use color_eyre::eyre::{Report, Result};
use itertools::Itertools;

struct Updates(Vec<Vec<isize>>);

impl FromStr for Updates {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let pages = s
            .lines()
            .map(|l| l.split(",").map(|n| n.parse::<isize>()).collect())
            .collect::<Result<_, _>>()?;
        Ok(Self(pages))
    }
}

impl Updates {
    fn get_valid(&self, rules: &OrderingRules) -> Self {
        let pages = self
            .0
            .clone()
            .into_iter()
            .filter(|p| rules.validate(p))
            .collect();
        Self(pages)
    }

    fn get_invalid(&self, rules: &OrderingRules) -> Self {
        let pages = self
            .0
            .clone()
            .into_iter()
            .filter(|p| !rules.validate(p))
            .collect();
        Self(pages)
    }
}

struct OrderingRules(Vec<(isize, isize)>);

impl OrderingRules {
    fn validate(&self, pnums: &Vec<isize>) -> bool {
        self.0.iter().all(|(a, b)| {
            let Some(a_pos) = pnums.iter().position(|&x| x == *a) else {
                return true;
            };
            let Some(b_pos) = pnums.iter().position(|&x| x == *b) else {
                return true;
            };
            a_pos < b_pos
        })
    }

    fn fix(&self, pnums: &Vec<isize>) -> Vec<isize> {
        let mut v = pnums.clone();

        v.sort_by(|a, b| {
            let mut fr = self
                .0
                .iter()
                .filter(|(ra, rb)| (ra == a || ra == b) && (rb == a || rb == b));
            if let Some((ra, _rb)) = fr.next() {
                if ra == a {
                    Ordering::Less
                } else {
                    Ordering::Greater
                }
            } else {
                Ordering::Equal
            }
        });
        v
    }
}

impl FromStr for OrderingRules {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let v = s
            .lines()
            .map(|l| {
                l.splitn(2, "|")
                    .map(|n| n.parse::<isize>().unwrap())
                    .collect_tuple()
                    .ok_or_else(|| Report::msg("Rules need two items"))
            })
            .collect::<Result<_, _>>()?;
        Ok(Self(v))
    }
}

fn parse(s: &str) -> Result<(OrderingRules, Updates)> {
    let parts: Vec<_> = s.splitn(2, "\n\n").collect();
    let rules = OrderingRules::from_str(parts[0])?;
    let updates = Updates::from_str(parts[1])?;
    Ok((rules, updates))
}

fn part1(filepath: &str) -> Result<isize> {
    let input = fs::read_to_string(filepath)?;
    let (rules, updates) = parse(&input)?;
    let res = updates
        .get_valid(&rules)
        .0
        .iter()
        .map(|v| v[v.len() / 2])
        .sum();
    Ok(res)
}

fn part2(filepath: &str) -> Result<isize> {
    let input = fs::read_to_string(filepath)?;
    let (rules, updates) = parse(&input)?;
    let res = updates
        .get_invalid(&rules)
        .0
        .iter()
        .map(|v| rules.fix(&v))
        .map(|v| v[v.len() / 2])
        .sum();
    Ok(res)
}

fn main() -> Result<()> {
    color_eyre::install()?;

    println!("Part 1: {}", part1("d05/input.txt")?);
    println!("Part 2: {}", part2("d05/input.txt")?);
    Ok(())
}

  

 zig

    
const std = @import("std");
const List = std.ArrayList;
const Map = std.AutoHashMap;

const tokenizeScalar = std.mem.tokenizeScalar;
const splitScalar = std.mem.splitScalar;
const parseInt = std.fmt.parseInt;
const print = std.debug.print;
const contains = std.mem.containsAtLeast;
const eql = std.mem.eql;

var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const alloc = gpa.allocator();

const Answer = struct {
    middle_sum: i32,
    reordered_sum: i32,
};

pub fn solve(input: []const u8) !Answer {
    var rows = splitScalar(u8, input, '\n');

    // key is a page number and value is a
    // list of pages to be printed before it
    var rules = Map(i32, List(i32)).init(alloc);
    var pages = List([]i32).init(alloc);
    defer {
        var iter = rules.iterator();
        while (iter.next()) |rule| {
            rule.value_ptr.deinit();
        }
        rules.deinit();
        pages.deinit();
    }

    var parse_rules = true;
    while (rows.next()) |row| {
        if (eql(u8, row, "")) {
            parse_rules = false;
            continue;
        }

        if (parse_rules) {
            var rule_pair = tokenizeScalar(u8, row, '|');
            const rule = try rules.getOrPut(try parseInt(i32, rule_pair.next().?, 10));
            if (!rule.found_existing) {
                rule.value_ptr.* = List(i32).init(alloc);
            }
            try rule.value_ptr.*.append(try parseInt(i32, rule_pair.next().?, 10));
        } else {
            var page = List(i32).init(alloc);
            var page_list = tokenizeScalar(u8, row, ',');
            while (page_list.next()) |list| {
                try page.append(try parseInt(i32, list, 10));
            }
            try pages.append(try page.toOwnedSlice());
        }
    }

    var middle_sum: i32 = 0;
    var reordered_sum: i32 = 0;

    var wrong_order = false;
    for (pages.items) |page| {
        var index: usize = page.len - 1;
        while (index > 0) : (index -= 1) {
            var page_rule = rules.get(page[index]) orelse continue;

            // check the rest of the pages
            var remaining: usize = 0;
            while (remaining < page[0..index].len) {
                if (contains(i32, page_rule.items, 1, &[_]i32{page[remaining]})) {
                    // re-order the wrong page
                    const element = page[remaining];
                    page[remaining] = page[index];
                    page[index] = element;
                    wrong_order = true;

                    if (rules.get(element)) |next_rule| {
                        page_rule = next_rule;
                    }

                    continue;
                }
                remaining += 1;
            }
        }
        if (wrong_order) {
            reordered_sum += page[(page.len - 1) / 2];
            wrong_order = false;
        } else {
            // middle page number
            middle_sum += page[(page.len - 1) / 2];
        }
    }
    return Answer{ .middle_sum = middle_sum, .reordered_sum = reordered_sum };
}

pub fn main() !void {
    const answer = try solve(@embedFile("input.txt"));
    print("Part 1: {d}\n", .{answer.middle_sum});
    print("Part 2: {d}\n", .{answer.reordered_sum});
}

test "test input" {
    const answer = try solve(@embedFile("test.txt"));
    try std.testing.expectEqual(143, answer.middle_sum);
    try std.testing.expectEqual(123, answer.reordered_sum);
}


  

 undefined

    
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.stream.Collectors;

public class Day05 {
    private static final Random random = new Random();

    public static void main(final String[] args) throws IOException {
        final String input = Files.readString(Path.of("2024\\05\\input.txt"), StandardCharsets.UTF_8);
        final String[] inputSplit = input.split("[\r\n]{4,}");

        final List<PageOrderingRule> rules = Arrays.stream(inputSplit[0].split("[\r\n]+"))
            .map(row -> row.split("\\|"))
            .map(row -> new PageOrderingRule(Integer.parseInt(row[0]), Integer.parseInt(row[1])))
            .toList();

        final List<ArrayList<Integer>> updates = Arrays.stream(inputSplit[1].split("[\r\n]+"))
            .map(row -> row.split(","))
            .map(row -> Arrays.stream(row).map(Integer::parseInt).collect(Collectors.toCollection(ArrayList::new)))
            .toList();

        System.out.println("Part 1: " + updates.stream()
            .filter(update -> validate(update, rules).isEmpty())
            .mapToInt(update -> update.get(update.size() / 2))
            .sum()
        );

        System.out.println("Part 2: " + updates.stream()
            .filter(update -> !validate(update, rules).isEmpty())
            .map(update -> fixOrder(update, rules))
            .mapToInt(update -> update.get(update.size() / 2))
            .sum()
        );
    }

    private static Set<Integer> validate(final List<Integer> update, final List<PageOrderingRule> rules) {
        final Set<Integer> invalidIndexes = new HashSet<>();

        for (int i = 0; i < update.size(); i++) {
            final Integer integer = update.get(i);
            for (final PageOrderingRule rule : rules) {
                if (rule.x == integer && update.contains(rule.y) && i > update.indexOf(rule.y)) {
                    invalidIndexes.add(i);
                }
                else if (rule.y == integer && update.contains(rule.x) && i < update.indexOf(rule.x)) {
                    invalidIndexes.add(i);
                }
            }
        }

        return invalidIndexes;
    }

    private static List<Integer> fixOrder(final List<Integer> update, final List<PageOrderingRule> rules) {
        List<Integer> invalidIndexesList = new ArrayList<>(validate(update, rules));

        // Swap randomly until the validation passes
        while (!invalidIndexesList.isEmpty()) {
            Collections.swap(update, random.nextInt(invalidIndexesList.size()), random.nextInt(invalidIndexesList.size()));
            invalidIndexesList = new ArrayList<>(validate(update, rules));
        }

        return update;
    }

    private static record PageOrderingRule(int x, int y) {}
}

  

 rust

    
use std::cmp::Ordering;

use crate::utils::{bytes_to_num, read_lines};

pub fn solution1() {
    let mut lines = read_input();
    let rules = parse_rules(&mut lines);

    let middle_rules_sum = lines
        .filter_map(|line| {
            let line_nums = rule_line_to_list(&line);
            line_nums
                .is_sorted_by(|&a, &b| is_sorted(&rules, (a, b)))
                .then_some(line_nums[line_nums.len() / 2])
        })
        .sum::<usize>();

    println!("Sum of in-order middle rules = {middle_rules_sum}");
}

pub fn solution2() {
    let mut lines = read_input();
    let rules = parse_rules(&mut lines);

    let middle_rules_sum = lines
        .filter_map(|line| {
            let mut line_nums = rule_line_to_list(&line);

            (!line_nums.is_sorted_by(|&a, &b| is_sorted(&rules, (a, b)))).then(|| {
                line_nums.sort_by(|&a, &b| {
                    is_sorted(&rules, (a, b))
                        .then_some(Ordering::Less)
                        .unwrap_or(Ordering::Greater)
                });

                line_nums[line_nums.len() / 2]
            })
        })
        .sum::<usize>();

    println!("Sum of middle rules = {middle_rules_sum}");
}

fn read_input() -> impl Iterator<Item = String> {
    read_lines("src/day5/input.txt")
}

fn parse_rules(lines: &mut impl Iterator<Item = String>) -> Vec<(usize, usize)> {
    lines
        .take_while(|line| !line.is_empty())
        .fold(Vec::new(), |mut rules, line| {
            let (a, b) = line.as_bytes().split_at(2);
            let a = bytes_to_num(a);
            let b = bytes_to_num(&b[1..]);

            rules.push((a, b));

            rules
        })
}

fn rule_line_to_list(line: &str) -> Vec<usize> {
    line.split(',')
        .map(|s| bytes_to_num(s.as_bytes()))
        .collect::<Vec<_>>()
}

fn is_sorted(rules: &[(usize, usize)], tuple: (usize, usize)) -> bool {
    rules.iter().any(|&r| r == tuple)
}


  

 undefined

    
defmodule AdventOfCode.Solution.Year2024.Day05 do
  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input) do
    [rules, pages_list] =
      String.split(input, "\n\n", limit: 2) |> Enum.map(&String.split(&1, "\n", trim: true))

    {for(rule <- rules, do: String.split(rule, "|") |> Enum.map(&String.to_integer/1))
     |> MapSet.new(),
     for(pages <- pages_list, do: String.split(pages, ",") |> Enum.map(&String.to_integer/1))}
  end

  def part1({rules, pages_list}), do: solve(rules, pages_list, false)

  def part2({rules, pages_list}), do: solve(rules, pages_list, true)

  def solve(rules, pages_list, negate) do
    for pages <- pages_list, reduce: 0 do
      total ->
        ordered = Enum.sort(pages, &([&1, &2] in rules))

        if negate != (ordered == pages),
          do: total + Enum.at(ordered, div(length(ordered), 2)),
          else: total
    end
  end
end