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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
- RagingHungryPanda ( @RagingHungryPanda@lemm.ee ) 1•4 days ago
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 - hades ( @hades@lemm.ee ) 5•10 days ago
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(); }
- lwhjp ( @lwhjp@lemmy.sdf.org ) 2•10 days ago
Oh! Sort first and then check for equality. Clever!
- hades ( @hades@lemm.ee ) 2•10 days ago
You’ll need to sort them anyway :)
(my first version of the first part only checked the order, without sorting).
- janAkali ( @janAkali@lemmy.one ) English5•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 msproc 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]
- sjmulder ( @sjmulder@lemmy.sdf.org ) 1•10 days ago
Nice, compact and easy to follow. The implicit
result
object reminds me of Visual Basic.
- proved_unglue ( @proved_unglue@programming.dev ) 4•10 days ago
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 }
- urquell ( @urquell@lemm.ee ) 2•10 days ago
I like how clean this is
- proved_unglue ( @proved_unglue@programming.dev ) 1•10 days ago
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 }
- urquell ( @urquell@lemm.ee ) 1•10 days ago
I wasn’t being sarcastic, but yeah even better
- Sparrow_1029 ( @Sparrow_1029@programming.dev ) 3•9 days ago
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 withu8
for all the pair values originally, but kept having to cast over and overas 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 thegrid
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 thesimple_grid::Grid
…Vec[idx]
access is faster maybe?I think you may have over thought it, I just applied the rules by swapping unordered pairs until it was ordered :D cool solution though
- janAkali ( @janAkali@lemmy.one ) English2•9 days ago
Good old bubble sort
Its called AdventOfCode, not AdventOfEfficientCode :D
- the_beber ( @the_beber@lemm.ee ) 2•9 days ago
Very cool approach. I didn’t think that far. I just wrote a compare function and hoped for the best.
- Andy ( @Andy@programming.dev ) 3•9 days ago
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 ;
- lwhjp ( @lwhjp@lemmy.sdf.org ) 3•10 days ago
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]
- ystael ( @ystael@beehaw.org ) 3•10 days ago
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
(respectivelyx \: y
) determines the permutation that would puty
in ascending (descending) order, then applies that permutation tox
.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
- Gobbel2000 ( @Gobbel2000@programming.dev ) 2•9 days ago
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 ) English2•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", &a, &b) != 2) break; assert(a>=0); assert(a=0); assert(b</b>
- reboot6675 ( @reboot6675@sopuli.xyz ) 1•10 days ago
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
- Ananace ( @ace@lemmy.ananace.dev ) 2•10 days ago
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) && 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}"); }
- solberg ( @solberg@lemmy.blahaj.zone ) English1•9 days ago
TypeScript
This one ended up being easier than I thought it was going to be. My algorithm for correcting the incorrect orders needed to be ran multiple times, for some reason
https://github.com/spencersolberg/advent-of-code-2024/tree/main/05
- reboot6675 ( @reboot6675@sopuli.xyz ) 1•10 days ago
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 < 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) }
- HeckGazer ( @HeckGazer@programming.dev ) 1•9 days ago
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 }
- madmo ( @madmo@programming.dev ) 1•10 days ago
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(&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(&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); }