Day 5: Print Queue

/* Advent of Code 2024
 * Day 05: Print Queue
 */

#import "Basic";
#import "File";
#import "Hash_Table";
#import "Sort";
#import "String";

// I'm not sure how to make page_compare() work without this being global.
ordering_rules: [..][2] int;

// The ordering rules map nicely to a comparison procedure. It feels really
// inefficient to iterate through the whole rules array for every comparison,
// but I'm not sure how else it could be done.
page_compare :: (a: int, b: int) -> int {
    for ordering_rules {
        if it[0] == a && it[1] == b {
            return -1;
        } else if it[0] == b && it[1] == a {
            return 1;
        }
    }

    return 0;
}

main :: () {
    input, success := read_entire_file("inputs/day_05.txt");
    assert(success);

    read_all_rules := false;
    correct_middle_page_sum := 0;
    incorrect_middle_page_sum := 0;

    for split(input, "\n") {
        // The two parts of the input are separated by a blank line. As usual,
        // we need to ignore the trailing newline if one exists in the input,
        // but this time we can't ignore the first one.
        if it == "" {
            if read_all_rules {
                continue;
            } else {
                read_all_rules = true;
            }
        }

        if !read_all_rules {
            pages := split(it, "|");
            array_add(
                *ordering_rules,
                .[string_to_int(pages[0]), string_to_int(pages[1])]
            );

            continue;
        }

        pages: [..] int;
        page_indices: Table(int, int);

        for split(it, ",") {
            page := string_to_int(it);
            array_add(*pages, page);
            table_add(*page_indices, page, it_index);
        }

        correctly_ordered := true;
        for ordering_rules {
            first_index,  found_first  := table_find(*page_indices, it[0]);
            second_index, found_second := table_find(*page_indices, it[1]);

            if found_first && found_second && first_index > second_index {
                correctly_ordered = false;
                break;
            }
        }

        if correctly_ordered {
            correct_middle_page_sum += pages[pages.count / 2];
        } else {
            sorted_pages := quick_sort(pages, page_compare);
            incorrect_middle_page_sum += sorted_pages[sorted_pages.count / 2];
        }
    }

    print(
        "Part 1: %\nPart 2: %\n",
        correct_middle_page_sum,
        incorrect_middle_page_sum
    );
}

import "utils" as utils;

let input = utils::get_input(5, false).split("\n\n");

let ordering_rules = input[0]
                .split("\n")
                .map(|line| line
                                .split("|")
                                .map(|id| id.parse_int()));

let page_updates = input[1]
                 .split("\n")
                 .map(|line| line
                                .split(",")
                                .map(|id| id.parse_int()));

// get all page numbers, deduplicated
let pages = [];
for rule in ordering_rules {
    pages.push(rule[0]);
    pages.push(rule[1]);
}

for update in page_updates {
    for page in update {
        pages.push(page);
    }
}

pages.sort();
pages.dedup();

// add a node for each page and keep a mapping of page to node and vice versa
let page_graph = new_graph();
let page_to_node = new_int_map();
let node_to_page = new_int_map();
for page in pages {
    let node = page_graph.add_node(0.0);
    page_to_node[page] = node;
    node_to_page[node.index()] = page;
}

// add ordering rules as nodes
for rule in ordering_rules {
    if rule[0] != rule[1] {
        page_graph.add_edge(page_to_node[rule[0]], page_to_node[rule[1]], 0.0);
    }
}

// PART 1
let total = 0;
for update in page_updates {
    // print(update);
    let valid = true;
    for i in 0..update.len()-1 {
        if page_graph.contains_edge(page_to_node[update[i+1]], page_to_node[update[i]]) {
            valid = false;
            break;
        }
    }
    if valid {
        total += update[update.len() / 2];
    }
}

print(`part 1: ${total}`);

// PART 2
let total = 0;
for update in page_updates {
    let valid = true;
    for i in 0..update.len()-1 {
        if page_graph.contains_edge(page_to_node[update[i+1]], page_to_node[update[i]]) {
            valid = false;
            break;
        }
    }
    if !valid {
        let i = 0;
        while i < update.len()-1 {
            if page_graph.contains_edge(page_to_node[update[i+1]], page_to_node[update[i]]) {
                let a = update[i];
                update[i] = update[i+1];
                update[i+1] = a;
                i = 0;
            } else {
                i += 1;
            }
        }
        total += update[update.len() / 2];
    }
}

print(`part 2: ${total}`);

def compute_p1(input)
  rules, updates = input.split("\n\n")
  rules = rules.lines.map { |line|
    line.split("|").map(&:to_i)
  }.sort
  updates = updates.lines.map { |line|
    line.split(",").map(&:to_i)
  }
  correct_updates = updates.filter { |update| check_update(rules, update) }
  return correct_updates.map { |update| update[update.length/2] }.sum
end

def check_update(rules, update)
  update.each_with_index do |page, idx|
    # for each page, verify that all rules put the following pages after, and
    # the preceeding pages before
    before = update[0...idx]
    before.each do |before_page|
      if is_rule?(rules, before_page, page)
        next
      elsif is_rule?(rules, page, before_page)
        return false
      end
    end

    after = update[(idx+1)...]
    after.each do |after_page|
      if is_rule?(rules, page, after_page)
        next
      elsif is_rule?(rules, after_page, page)
        return false
      end
    end
  end
  return true
end

def is_rule?(rules, before, after)
  rules.index([before, after])
end

def compute_p2(input)
  rules, updates = input.split("\n\n")
  rules = rules.lines.map { |line|
    line.split("|").map(&:to_i)
  }.sort
  updates = updates.lines.map { |line|
    line.split(",").map(&:to_i)
  }
  incorrect_updates = updates.filter { |update| ! check_update(rules, update) }
  return incorrect_updates.map { |update| fix_update(rules, update) }.map { |update| update[update.length/2] }.sum
end

def fix_update(rules, update)
  return update.sort { |a, b|
    if is_rule?(rules, a, b)
      -1
    elsif is_rule?(rules, b, a)
      1
    else
      0
    end
  }
end

from collections import defaultdict
import itertools
import sys

def is_correctly_ordered(rules: defaultdict[int, list[int]], update: list[int]) -> bool:
    for x, y in itertools.pairwise(update):
        if x in rules[y]:
            return False
    return True

rules_input, updates_input = sys.stdin.read().split('\n\n')
rules = defaultdict[int, list[int]](list)
for line in rules_input.split('\n'):
    x, y = map(int, line.split('|'))
    rules[x].append(y)

total = 0
for line in updates_input.strip().split('\n'):
    update = [*map(int, line.split(','))]
    if is_correctly_ordered(rules, update):
        total += update[len(update) // 2]

print(total)

from collections import defaultdict
import functools
import itertools
import sys

def is_correctly_ordered(rules: defaultdict[int, list[int]], update: list[int]) -> bool:
    for x, y in itertools.pairwise(update):
        if x in rules[y]:
            return False
    return True

# XXX: relies on rules being global (cmp_to_key functions take exactly 2 args)
def cmp(x: int, y: int) -> int:
    if x in rules[y]:
        return 1
    elif y in rules[x]:
        return -1
    else:
        return 0

rules_input, updates_input = sys.stdin.read().split('\n\n')
rules = defaultdict[int, list[int]](list)
for line in rules_input.split('\n'):
    x, y = map(int, line.split('|'))
    rules[x].append(y)

total = 0
for line in updates_input.strip().split('\n'):
    update = [*map(int, line.split(','))]
    if not is_correctly_ordered(rules, update):
        fixed = sorted(update, key=functools.cmp_to_key(cmp))
        total += fixed[len(fixed) // 2]

print(total)

Edit: I went back and used a closure returning a lambda to clean up that awkward cmp function. Before it relied on rules being global, since functools.cmp_to_key functions take exactly 2 arguments.

def cmp_with_rules(rules: defaultdict[int, list[int]]) -> Callable[[int, int], int]:
    return lambda x, y: 1 if x in rules[y] else (-1 if y in rules[x] else 0)

My solution leans on JS's Array.prototype.sort(). I built a predicate function that takes the two page numbers being compared and looks for a rule that includes both of them (in either order). Then it returns either 1 or -1 depending on the rule. Since it's only concerned with two page numbers at a time, and only a single rule that governs those two specific numbers, it's quite fast.

For Part 1 I sorted every update and compared the sorted list against the original. This worked in my favor for Part 2, which needed to count sorted (corrected) updates, so I made a single shared function to do the heavy lifting and just pass it a group flag to indicate whether the already-correct or newly sorted previously-correct updates are wanted.

type InputData = [Rules, Updates];

type Rules = [number, number][];
type Updates = number[][];

enum UpdateGroup {
  Correct,
  Incorrect,
}

function formatInput(input: string): InputData {
  const [rules, updates] = input.trim().split('\n\n');
  return [
    rules.split('\n').map(rule => rule.split('|').map(Number)) as Rules,
    updates.split('\n').map(update => update.split(',').map(Number)),
  ];
}

export function run(input: string): string[] {
  const data = formatInput(input);

  const countUpdates = ([rules, updates]: InputData, group: UpdateGroup): number => {
    let total = 0;
    for (const update of updates) {
      const sortedUpdate = [...update].sort((a, b) => {
        const matchingRule = rules.find(rule => (rule[0] === a && rule[1] === b) || (rule[0] === b && rule[1] === a));
        return a === matchingRule[0] ? -1 : 1;
      });
      if (
        (group === UpdateGroup.Correct && sortedUpdate.join() === update.join()) ||
        (group === UpdateGroup.Incorrect && sortedUpdate.join() !== update.join())
      ) {
        const middlePage = sortedUpdate[Math.floor(sortedUpdate.length / 2)];
        total += middlePage;
      }
    }
    return total;
  };

  const identifyCorrectUpdates = (pageData: InputData): number => {
    return countUpdates(pageData, UpdateGroup.Correct);
  };

  const identifyIncorrectUpdates = (pageData: InputData): number => {
    return countUpdates(pageData, UpdateGroup.Incorrect);
  };

  return [`${identifyCorrectUpdates(data)}`, `${identifyIncorrectUpdates(data)}`];
}

I decided to use a lot of comprehensions for this one, for no particular reason.

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

  @typep page :: integer

  @impl true
  @spec parse(String.t()) :: {
          # k comes before all pages in v
          %{page => MapSet.t(page)},
          [[page]]
        }
  def parse(input) do
    [rules, updates] = String.split(input, "\n\n", trim: true)
    {parse_afters(rules), parse_updates(updates)}
  end

  defp parse_afters(rules) do
    for rule <- String.split(rules, "\n", trim: true), reduce: %{} do
      afters ->
        [before, after_] = for page <- String.split(rule, "|"), do: String.to_integer(page)

        afters
        |> Map.update(before, MapSet.new([after_]), &MapSet.put(&1, after_))
        # Adds an entry for the last page (which has no afters)
        |> Map.put_new(after_, MapSet.new())
    end
  end

  defp parse_updates(updates) do
    for update <- String.split(updates, "\n", trim: true) do
      for page <- String.split(update, ",") do
        String.to_integer(page)
      end
    end
  end

  def part1({afters, updates}) do
    for(update <- updates, ordered?(update, afters), do: update)
    |> sum_middles()
  end

  def part2({afters, updates}) do
    for(update <- updates, sorted = sorted_or_nil(update, afters), sorted != nil, do: sorted)
    |> sum_middles()
  end

  defp ordered?(update, afters) do
    update
    |> Enum.chunk_every(2, 1, :discard)
    |> Enum.all?(&page_pair_ordered?(&1, afters))
  end

  defp sorted_or_nil(update, afters) do
    case Enum.sort(update, &page_pair_ordered?([&1, &2], afters)) do
      ^update -> nil
      sorted -> sorted
    end
  end

  defp page_pair_ordered?([l, r], afters), do: r in afters[l]

  defp sum_middles(updates) do
    for update <- updates, reduce: 0 do
      acc -> acc + Enum.at(update, div(length(update), 2))
    end
  end
end

Pretty straightforward. I iterate through each page then go through its rules to see if I already encountered anything that is defined to come after it.

#!/usr/bin/awk -f
BEGIN { FS = "[|,]" }
/\|/ { rule[$1] = rule[$1] $2 "," }
/^[^\|]*$/ {
	for (i in pages) delete pages[i]

	for (i = 1; i <= NF; ++i) {
		pages[$i] = 1
		r = rule[$i]
		n = split(r, a, ",")
		for (j = 1; j < n; ++j)
			if (pages[a[j]])
				next
	}

	total += $(int(NF/2)+1)
}
END { print total }

As I have mentioned quite a few times here already, AWK doesn't provide any sorting option, much less an advanced one where you can provide custom rules or weights, so I was initially worried about this. However, I decided to try the naive approach of simply swapping the pages in each violation until they were sorted and it worked surprisingly well.

#!/usr/bin/awk -f
BEGIN { FS = "[|,]" }
/\|/ { rule[$1] = rule[$1] $2 "," }
/^[^\|]*$/ {
	# clean up all arrays and variables from previous iterations
	# in hindsight, there would probably be less of this boilerplate if I used a function instead
	for (i in pages) delete pages[i]
	for (i in order) delete order[i]
	temp = 0

	# set this separately now since it will be modified during the loop
	for (i = 1; i <= NF; ++i) order[i] = $i

	for (i = 1; i <= NF; ++i) {
		pages[order[i]] = i
		r = rule[order[i]]
		n = split(r, a, ",")
		for (j = 1; j < n; ++j)
			if (pages[a[j]]) {
				# swap the places of the updates in the rule violated
				temp = order[i]
				order[i] = a[j]
				order[pages[a[j]]] = temp

				# restart the processing again to correct any cascading errors
				for (i in pages) delete pages[i]
				i = 0
				break
			}
	}

	if (temp)
		total += order[int(NF/2)+1]
}
END { print total }

#! /usr/bin/env racket
#lang racket

(require rackunit)

;; XXX: these two could be a single proc that takes a separator
;; parse out all of the page rules
(define (parse-rules in-port [rules empty])
  ;; helper procedure for parsing a single rule
  (define (parse-rule rule)
    (map string->number
         (string-split rule "|")))
  (let ([line (read-line in-port)])
    (cond
      [(eof-object? line) (reverse rules)]
      [else (parse-rules in-port
                         (cons (parse-rule line)
                               rules))])))
;; parse out all of the required pages
(define (parse-pages in-port [pages empty])
  ;; helper procedure for parsing a single rule
  (define (parse-page rule)
    (map string->number
         (string-split rule ",")))
  (let ([line (read-line in-port)])
    (cond
      [(eof-object? line) (reverse pages)]
      [else (parse-pages in-port
                         (cons (parse-page line)
                               pages))])))

;; returns #t if a given set of pages is a valid order based on the given page-rules
(define (valid? pages rules)
  ;; helper procedure that checks the set of pages against a single rule
  (define (valid?-helper pages rule)
    (let ([first (index-of pages (car rule))]
          [second (index-of pages(list-ref rule 1))])
      (cond
        [(not (and first second)) #t]
        [else (> second first)])))

  (cond
    [(empty? rules) #t]
    [else (and (valid?-helper pages (car rules))
               (valid? pages (cdr rules)))]))

;; return the middle index of a list
(define (middle page-set)
  (let ([i (quotient (length page-set) 2)])
    (list-ref page-set i)))

(define (day05/run-part01 rules-port pages-port)
  (let ([rules (parse-rules rules-port)]
        [pages (parse-pages pages-port)])
    (for/fold ([sum-middle-valid 0])
              ([page-set pages])
      (cond
        [(valid? page-set rules) (+ sum-middle-valid (middle page-set))]
        [else sum-middle-valid]))))
(define (day05/run-part02 in-port) null)

(check-equal? (day05/run-part01 (open-input-file "examples/day05_rules.in")
                                (open-input-file "examples/day05_pages.in"))
              143
              "Test part 1")
(check-equal? (day05/run-part02 (open-input-file "examples/day05_rules.in")) null "Test part 2")

(let* ([rule-port (open-input-file "inputs/day05_rules.in")]
       [pages-port (open-input-file "inputs/day05_pages.in")]
       [part1 (day05/run-part01 rule-port pages-port)]
       [part2 (day05/run-part02 0)])
  (printf "Part 1: ~a, Part 2: ~a\n" part1 part2))

#! /usr/bin/env racket
#lang racket

(require graph rackunit)

;; XXX: these two could be a single proc that takes a separator
;; parse out all of the page rules
(define (parse-rules in-port [rules empty])
  ;; helper procedure for parsing a single rule
  (define (parse-rule rule)
    (map string->number
         (string-split rule "|")))
  (let ([line (read-line in-port)])
    (cond
      [(eof-object? line) (reverse rules)]
      [else (parse-rules in-port
                         (cons (parse-rule line)
                               rules))])))
;; parse out all of the updates
(define (parse-updates in-port [pages empty])
  ;; helper procedure for parsing a single rule
  (define (parse-update rule)
    (map string->number
         (string-split rule ",")))
  (let ([line (read-line in-port)])
    (cond
      [(eof-object? line) (reverse pages)]
      [else (parse-updates in-port
                           (cons (parse-update line)
                                 pages))])))

;; returns #t if a given update is valid for the given rules
(define (valid? update rules)
  ;; helper procedure that checks the update against a single rule
  (define (valid?-helper update rule)
    (let ([first (index-of update (car rule))]
          [second (index-of update(list-ref rule 1))])
      (cond
        [(not (and first second)) #t]
        [else (> second first)])))

  (cond
    [(empty? rules) #t]
    [else (and (valid?-helper update (car rules))
               (valid? update (cdr rules)))]))

;; return the middle index of a list
(define (list-middle lst)
  (let ([i (quotient (length lst) 2)])
    (list-ref lst i)))

;; sort an update based on the gives rules
(define (update-sort update rules)
  (let* ([filtered-rules (filter (lambda (rule)
                                   (and (member (first rule) update)
                                        (member (second rule) update)))
                                 rules)]
         [update-graph (directed-graph filtered-rules)])
    (tsort update-graph)))

;; do the math for p1
(define (day05/run-part01 updates)
  (for/fold ([sum-middle 0])
            ([update (in-list updates)])
    (+ sum-middle (list-middle update))))

;; do the math for p2
(define (day05/run-part02 updates rules)
  (for/fold ([sum-middle 0])
            ([update (in-list updates)])
    (+ sum-middle (list-middle (update-sort update rules)))))

;; run using the test inputs
(let* ([rules-port (open-input-file "examples/day05_rules.in")]
       [updates-port (open-input-file "examples/day05_updates.in")]
       [rules (parse-rules rules-port)]
       [updates (parse-updates updates-port)]
       [valid-updates (filter (lambda (update)
                                (valid? update rules))
                              updates)]
       [invalid-updates (filter (lambda (update)
                                  (not (member update valid-updates)))
                                updates)]
       [part1 (day05/run-part01 valid-updates)]
       [part2 (day05/run-part02 invalid-updates rules)])
  (and (check-equal? part1 143 "Test part 1")
       (check-equal? part2 123 "Test part 2")))

;; run with my reala input
(let* ([rules-port (open-input-file "inputs/day05_rules.in")]
       [updates-port (open-input-file "inputs/day05_updates.in")]
       [rules (parse-rules rules-port)]
       [updates (parse-updates updates-port)]
       [valid-updates (filter (lambda (update)
                                (valid? update rules))
                              updates)]
       [invalid-updates (filter (lambda (update)
                                  (not (member update valid-updates)))
                                updates)]
       [part1 (day05/run-part01 valid-updates)]
       [part2 (day05/run-part02 invalid-updates rules)])
  (and (check-equal? part1 7074 "Test part 1")
       (check-equal? part2 4828 "Test part 2"))
  (printf "Part 1: ~a, Part 2: ~a\n" part1 part2))