Day 5: Print Queue

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • I’ve got a “smart” solution and a really dumb one. I’ll start with the smart one (incomplete but you can infer). I did four different ways to try to get it faster, less memory, etc.

    // 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())
            .Middle()
        );
    

    The dumb solution. These comparisons aren’t fully transitive. I can’t believe it works.

    public static SortedSet Sort3(Page[] line,
        Dictionary> rules)
    {
        // how the hell is this working?
        var sorted = new SortedSet(new Sort3Comparer(rules));
        foreach (var page in line)
            sorted.Add(page);
        return sorted;
    }
    
    public static Page[] OrderBy(Page[] line, Dictionary> rules)
    {
        return line.OrderBy(identity, new Sort3Comparer(rules)).ToArray();
    }
    
    sealed class Sort3Comparer : IComparer
    {
        private readonly Dictionary> _rules;
    
        public Sort3Comparer(Dictionary> 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;
        }
    }
    
    Method Mean Error StdDev Gen0 Gen1 Allocated
    Part2_UsingList (literally just Insert) 660.3 us 12.87 us 23.20 us 187.5000 35.1563 1144.86 KB
    Part2_TrackLinkedList (wrong now) 1,559.7 us 6.91 us 6.46 us 128.9063 21.4844 795.03 KB
    Part2_TopologicalSort 732.3 us 13.97 us 16.09 us 285.1563 61.5234 1718.36 KB
    Part2_SortedSet 309.1 us 4.13 us 3.45 us 54.1992 10.2539 328.97 KB
    Part2_OrderBy 304.5 us 6.09 us 9.11 us 48.8281 7.8125 301.29 KB
  • C#

    using QuickGraph;
    using QuickGraph.Algorithms.TopologicalSort;
    public class Day05 : Solver
    {
      private List updates;
      private List 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>();
          graph.AddVertexRange(update);
          graph.AddEdgeRange(rules
            .Where(rule => update.Contains(rule.Item1) && update.Contains(rule.Item2))
            .Select(rule => new Edge(rule.Item1, rule.Item2)));
          List ordered_update = [];
          new TopologicalSortAlgorithm>(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();
    }
    
  •  janAkali   ( @janAkali@lemmy.one ) 
    link
    fedilink
    English
    5
    edit-2
    10 days ago

    Nim

    Solution: sort numbers using custom rules and compare if sorted == original. Part 2 is trivial.
    Runtime for both parts: 1.05 ms

    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]
    

    Codeberg repo

  • Kotlin

    Took me a while to figure out how to sort according to the rules. 🤯

    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, rules: List>): List {
        return numbers.sortedWith { a, b -> if (rules.contains(a to b)) -1 else 1 }
    }
    
    private fun parse(input: String): Pair>, List>> {
        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
    }
    
      • I guess adding type aliases and removing the regex from parser makes it a bit more readable.

        typealias Rule = Pair
        typealias PageNumbers = List
        
        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: PageNumbers, rules: List): PageNumbers {
            return numbers.sortedWith { a, b -> if (rules.contains(a to b)) -1 else 1 }
        }
        
        private fun parse(input: String): Pair, List> {
            val (rulesSection, numbersSection) = input.split("\n\n")
            val rules = rulesSection.lines()
                .mapNotNull { line ->
                    val parts = line.split('|').map { it.toInt() }
                    if (parts.size >= 2) parts[0] to parts[1] else null
                }
            val numbers = numbersSection.lines()
                .map { line -> line.split(',').map { it.toInt() } }
            return rules to numbers
        }
        
  • Rust

    Real thinker. Messed around with a couple solutions before this one. The gist is to take all the pairwise comparisons given and record them for easy access in a ranking matrix.

    For the sample input, this grid would look like this (I left out all the non-present integers, but it would be a 98 x 98 grid where all the empty spaces are filled with Ordering::Equal):

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

    I discovered this can’t be used for a total order on the actual puzzle input because there were cycles in the pairs given (see how rust changed sort implementations as of 1.81). I used usize for convenience (I did it with u8 for all the pair values originally, but kept having to cast over and over as usize). Didn’t notice a performance difference, but I’m sure uses a bit more memory.

    Also I Liked the simple_grid crate a little better than the grid one. Will have to refactor that out at some point.

    solution
    use std::{cmp::Ordering, fs::read_to_string};
    
    use simple_grid::Grid;
    
    type Idx = (usize, usize);
    type Matrix = Grid;
    type Page = Vec;
    
    fn parse_input(input: &str) -> (Vec, Vec) {
        let split: Vec<&str> = input.split("\n\n").collect();
        let (pair_str, page_str) = (split[0], split[1]);
        let pairs = parse_pairs(pair_str);
        let pages = parse_pages(page_str);
        (pairs, pages)
    }
    
    fn parse_pairs(input: &str) -> Vec {
        input
            .lines()
            .map(|l| {
                let (a, b) = l.split_once('|').unwrap();
                (a.parse().unwrap(), b.parse().unwrap())
            })
            .collect()
    }
    
    fn parse_pages(input: &str) -> Vec {
        input
            .lines()
            .map(|l| -> Page {
                l.split(",")
                    .map(|d| d.parse::().expect("invalid digit"))
                    .collect()
            })
            .collect()
    }
    
    fn create_matrix(pairs: &[Idx]) -> Matrix {
        let max = *pairs
            .iter()
            .flat_map(|(a, b)| [a, b])
            .max()
            .expect("iterator is non-empty")
            + 1;
        let mut matrix = Grid::new(max, max, vec![Ordering::Equal; max * max]);
        for (a, b) in pairs {
            matrix.replace_cell((*a, *b), Ordering::Less);
            matrix.replace_cell((*b, *a), Ordering::Greater);
        }
        matrix
    }
    
    fn valid_pages(pages: &[Page], matrix: &Matrix) -> usize {
        pages
            .iter()
            .filter_map(|p| {
                if check_order(p, matrix) {
                    Some(p[p.len() / 2])
                } else {
                    None
                }
            })
            .sum()
    }
    
    fn fix_invalid_pages(pages: &mut [Page], matrix: &Matrix) -> usize {
        pages
            .iter_mut()
            .filter(|p| !check_order(p, matrix))
            .map(|v| {
                v.sort_by(|a, b| *matrix.get((*a, *b)).unwrap());
                v[v.len() / 2]
            })
            .sum()
    }
    
    fn check_order(page: &[usize], matrix: &Matrix) -> bool {
        page.is_sorted_by(|a, b| *matrix.get((*a, *b)).unwrap() == Ordering::Less)
    }
    
    pub fn solve() {
        let input = read_to_string("inputs/day05.txt").expect("read file");
        let (pairs, mut pages) = parse_input(&input);
        let matrix = create_matrix(&pairs);
        println!("Part 1: {}", valid_pages(&pages, &matrix));
        println!("Part 2: {}", fix_invalid_pages(&mut pages, &matrix));
    }
    

    On github

    *Edit: I did try switching to just using std::collections::HashMap, but it was 0.1 ms slower on average than using the simple_grid::GridVec[idx] access is faster maybe?

  • Factor

    : 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 ;
    

    on GitHub

  • Haskell

    Part two was actually much easier than I thought it was!

    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]
    
  • J

    This is a problem where J’s biases lead one to a very different solution from most of the others. The natural representation of a directed graph in J is an adjacency matrix, and sorting is specified in terms of a permutation to apply rather than in terms of a comparator: x /: y (respectively x \: y) determines the permutation that would put y in ascending (descending) order, then applies that permutation to x.

    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
    
  • Rust

    While part 1 was pretty quick, part 2 took me a while to figure something out. I figured that the relation would probably be a total ordering, and obtained the actual order using topological sorting. But it turns out the relation has cycles, so the topological sort must be limited to the elements that actually occur in the lists.

    Solution
    use std::collections::{HashSet, HashMap, VecDeque};
    
    fn parse_lists(input: &str) -> Vec> {
        input.lines()
            .map(|l| l.split(',').map(|e| e.parse().unwrap()).collect())
            .collect()
    }
    
    fn parse_relation(input: String) -> (HashSet<(u32, u32)>, Vec>) {
        let (ordering, lists) = input.split_once("\n\n").unwrap();
        let relation = ordering.lines()
            .map(|l| {
                let (a, b) = l.split_once('|').unwrap();
                (a.parse().unwrap(), b.parse().unwrap())
            })
            .collect();
        (relation, parse_lists(lists))
    }
    
    fn parse_graph(input: String) -> (Vec>, Vec>) {
        let (ordering, lists) = input.split_once("\n\n").unwrap();
        let mut graph = Vec::new();
        for l in ordering.lines() {
            let (a, b) = l.split_once('|').unwrap();
            let v: u32 = a.parse().unwrap();
            let w: u32 = b.parse().unwrap();
            let new_len = v.max(w) as usize + 1;
            if new_len > graph.len() {
                graph.resize(new_len, Vec::new())
            }
            graph[v as usize].push(w);
        }
        (graph, parse_lists(lists))
    }
    
    
    fn part1(input: String) {
        let (relation, lists) = parse_relation(input); 
        let mut sum = 0;
        for l in lists {
            let mut valid = true;
            for i in 0..l.len() {
                for j in 0..i {
                    if relation.contains(&(l[i], l[j])) {
                        valid = false;
                        break
                    }
                }
                if !valid { break }
            }
            if valid {
                sum += l[l.len() / 2];
            }
        }
        println!("{sum}");
    }
    
    
    // Topological order of graph, but limited to nodes in the set `subgraph`.
    // Otherwise the graph is not acyclic.
    fn topological_sort(graph: &[Vec], subgraph: &HashSet) -> Vec {
        let mut order = VecDeque::with_capacity(subgraph.len());
        let mut marked = vec![false; graph.len()];
        for &v in subgraph {
            if !marked[v as usize] {
                dfs(graph, subgraph, v as usize, &mut marked, &mut order)
            }
        }
        order.into()
    }
    
    fn dfs(graph: &[Vec], subgraph: &HashSet, v: usize, marked: &mut [bool], order: &mut VecDeque) {
        marked[v] = true;
        for &w in graph[v].iter().filter(|v| subgraph.contains(v)) {
            if !marked[w as usize] {
                dfs(graph, subgraph, w as usize, marked, order);
            }
        }
        order.push_front(v as u32);
    }
    
    fn rank(order: &[u32]) -> HashMap {
        order.iter().enumerate().map(|(i, x)| (*x, i as u32)).collect()
    }
    
    // Part 1 with topological sorting, which is slower
    fn _part1(input: String) {
        let (graph, lists) = parse_graph(input);
        let mut sum = 0;
        for l in lists {
            let subgraph = HashSet::from_iter(l.iter().copied());
            let rank = rank(&topological_sort(&graph, &subgraph));
            if l.is_sorted_by_key(|x| rank[x]) {
                sum += l[l.len() / 2];
            }
        }
        println!("{sum}");
    }
    
    fn part2(input: String) {
        let (graph, lists) = parse_graph(input);
        let mut sum = 0;
        for mut l in lists {
            let subgraph = HashSet::from_iter(l.iter().copied());
            let rank = rank(&topological_sort(&graph, &subgraph));
            if !l.is_sorted_by_key(|x| rank[x]) {
                l.sort_unstable_by_key(|x| rank[x]);            
                sum += l[l.len() / 2];
            }
        }
        println!("{sum}");
    }
    
    util::aoc_main!();
    

    also on github

  •  sjmulder   ( @sjmulder@lemmy.sdf.org ) 
    link
    fedilink
    English
    2
    edit-2
    10 days ago

    C

    I got the question so wrong - I thought a|b and b|c would imply a|c so I went and used dynamic programming to propagate indirect relations through a table.

    It worked beautifully but not for the input, which doesn’t describe an absolute global ordering at all. It may well give a|c and b|c AND c|a. Nothing can be deduced then, and nothing needs to, because all required relations are directly specified.

    The table works great though, the sort comparator is a simple 2D array index, so O(1).

    Code
    #include "common.h"
    
    #define TSZ 100
    #define ASZ 32
    
    /* tab[a][b] is -1 if a<b>b */
    static int8_t tab[TSZ][TSZ];
    
    static int
    cmp(const void *a, const void *b)
    {
    	return tab[*(const int *)a][*(const int *)b];
    }
    
    int
    main(int argc, char **argv)
    {
    	char buf[128], *rest, *tok;
    	int p1=0,p2=0, arr[ASZ],srt[ASZ], n,i, a,b;
    
    	if (argc > 1)
    		DISCARD(freopen(argv[1], "r", stdin));
    	
    	while (fgets(buf, sizeof(buf), stdin)) {
    		if (sscanf(buf, "%d|%d", &amp;a, &amp;b) != 2)
    			break;
    		assert(a>=0); assert(a=0); assert(b</b>
    • Same, I initially also thought a|b and a|c implies a|c. However when I drew the graph of the example on paper, I suspected that all relations will be given, and coded it with that assumption, that turned out to be correct

  • Well, this one ended up with a surprisingly easy part 2 with how I wrote it.
    Not the most computationally optimal code, but since they’re still cheap enough to run in milliseconds I’m not overly bothered.

    C#
    class OrderComparer : IComparer
    {
      Dictionary> ordering;
      public OrderComparer(Dictionary> ordering) {
        this.ordering = ordering;
      }
    
      public int Compare(int x, int y)
      {
        if (ordering.ContainsKey(x) &amp;&amp; ordering[x].Contains(y))
          return -1;
        return 1;
      }
    }
    
    Dictionary> ordering = new Dictionary>();
    int[][] updates = new int[0][];
    
    public void Input(IEnumerable lines)
    {
      foreach (var pair in lines.TakeWhile(l => l.Contains('|')).Select(l => l.Split('|').Select(w => int.Parse(w))))
      {
        if (!ordering.ContainsKey(pair.First()))
          ordering[pair.First()] = new List();
        ordering[pair.First()].Add(pair.Last());
      }
      updates = lines.SkipWhile(s => s.Contains('|') || string.IsNullOrWhiteSpace(s)).Select(l => l.Split(',').Select(w => int.Parse(w)).ToArray()).ToArray();
    }
    
    public void Part1()
    {
      int correct = 0;
      var comparer = new OrderComparer(ordering);
      foreach (var update in updates)
      {
        var ordered = update.Order(comparer);
        if (update.SequenceEqual(ordered))
          correct += ordered.Skip(ordered.Count() / 2).First();
      }
    
      Console.WriteLine($"Sum: {correct}");
    }
    public void Part2()
    {
      int incorrect = 0;
      var comparer = new OrderComparer(ordering);
      foreach (var update in updates)
      {
        var ordered = update.Order(comparer);
        if (!update.SequenceEqual(ordered))
          incorrect += ordered.Skip(ordered.Count() / 2).First();
      }
    
      Console.WriteLine($"Sum: {incorrect}");
    }
    
  • Go

    Using a map to store u|v relations. Part 2 sorting with a custom compare function worked very nicely

    spoiler
    func main() {
    	file, _ := os.Open("input.txt")
    	defer file.Close()
    	scanner := bufio.NewScanner(file)
    
    	mapPages := make(map[string][]string)
    	rulesSection := true
    	middleSumOk := 0
    	middleSumNotOk := 0
    
    	for scanner.Scan() {
    		line := scanner.Text()
    		if line == "" {
    			rulesSection = false
    			continue
    		}
    
    		if rulesSection {
    			parts := strings.Split(line, "|")
    			u, v := parts[0], parts[1]
    			mapPages[u] = append(mapPages[u], v)
    		} else {
    			update := strings.Split(line, ",")
    			isOk := true
    
    			for i := 1; i &lt; len(update); i++ {
    				u, v := update[i-1], update[i]
    				if !slices.Contains(mapPages[u], v) {
    					isOk = false
    					break
    				}
    			}
    
    			middlePos := len(update) / 2
    			if isOk {
    				middlePage, _ := strconv.Atoi(update[middlePos])
    				middleSumOk += middlePage
    			} else {
    				slices.SortFunc(update, func(u, v string) int {
    					if slices.Contains(mapPages[u], v) {
    						return -1
    					} else if slices.Contains(mapPages[v], u) {
    						return 1
    					}
    					return 0
    				})
    				middlePage, _ := strconv.Atoi(update[middlePos])
    				middleSumNotOk += middlePage
    			}
    		}
    	}
    
    	fmt.Println("Part 1:", middleSumOk)
    	fmt.Println("Part 2:", middleSumNotOk)
    }
    
    • Because you’re just sorting integers and in a single pass, the a == b and a > b distinction doesn’t actually matter here, so the cmp can very simply be is a|b in rules, no map needed.

      Edit: I realise it would be a sidegrade for your case because of how you did P1, just thought it was an interesting insight, especially for those that did P1 by checking if the input was sorted using the same custom compare.

      func solution(input string) (int, int) {
      	// rules: ["a|b", ...]
      	// updates: [[1, 2, 3, 4], ...]
      	var rules, updates = parse(input)
      
      	sortFunc := func(a int, b int) int {
      		if slices.Contains(rules, strconv.Itoa(a)+"|"+strconv.Itoa(b)) {
      			return -1
      		}
      		return 1
      	}
      
      	var sumOrdered = 0
      	var sumUnordered = 0
      	for _, update := range updates {
      		if slices.IsSortedFunc(update, sortFunc) {
      			sumOrdered += update[len(update)/2]
      		} else {
      			slices.SortStableFunc(update, sortFunc)
      			sumUnordered += update[len(update)/2]
      		}
      	}
      	return sumOrdered, sumUnordered
      }
  • Rust

    Used a sorted/unsorted comparison to solve the first part, the second part was just filling out the else branch.

    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> = 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::())
                .collect::, _>>()
                .unwrap();
    
            let left = lr[0];
            let right = lr[1];
    
            if let Some(values) = rules.get_mut(&amp;left) {
                values.push(right);
                values.sort();
            } else {
                rules.insert(left, vec![right]);
            }
        }
    
        let mut updates: Vec> = Vec::default();
    
        for line in lines {
            let line = line.unwrap();
    
            let update = line
                .split(',')
                .map(|el| el.parse::())
                .collect::, _>>()
                .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(&amp;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);
    }