this post was submitted on 05 Dec 2024
25 points (100.0% liked)

Advent Of Code

920 readers
25 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
 

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

(page 2) 7 comments
sorted by: hot top controversial new old
[โ€“] hosaka@programming.dev 1 points 2 weeks ago

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);
}

[โ€“] Rin@lemm.ee 1 points 2 weeks ago

TypeScript

Solution

import { AdventOfCodeSolutionFunction } from "./solutions";

type RulesType = Map<number, Array<number>>;

const ReduceMiddleNumbers = (p: number, v: Array<number>) => p + v[(v.length - 1) / 2];

const CheckPages = (pages: Array<number>, rules: RulesType): [true] | [false, number, number] => {
    for (let index = 0; index < pages.length; index++) {
        const page = pages[index]; // [97,61,53,29,13] => 97
        const elementRules = rules.get(page);

        // there are no rules for this number
        if (elementRules === undefined)
            continue;

        for (let ruleIndex = 0; ruleIndex < elementRules.length; ruleIndex++) {
            const rule = elementRules[ruleIndex];
            const rulePos = pages.indexOf(rule);

            // the number specified in the rule doesn't exist in our page
            if (rulePos == -1)
                continue;

            // the number came before our current index, meaning it's bad.
            if (index > rulePos) 
                return [false, index, rulePos];
        }
    }

    return [true];
}


const Reposition = (pages: Array<number>, rules: RulesType) => {
    const newPages = [...pages];
    let res = CheckPages(newPages, rules);
    let i = 0; 
    // this will be public facing api and it's possible to create inf loops so, 10k limit
    while(!res[0] && i++ < 10000) {
        // yes I know the trick, but tricks < semantics
        const moveThisRight = newPages[res[1]];
        const moveThisLeft = newPages[res[2]];
        newPages[res[1]] = moveThisLeft;
        newPages[res[2]] = moveThisRight;

        res = CheckPages(newPages, rules);
    }

    return [...newPages];
}

export const solution_5: AdventOfCodeSolutionFunction = (input) => {
    const [rules_input, content_input] = input.split("\n\n").map(v => v.trim());

    const rules: RulesType = new Map();

    rules_input.split("\n").map(v => v.split("|").map(v => Number(v))).forEach((rule) => {
        const [k, v] = rule;
        if (rules.has(k))
            rules.get(k)!.push(v);
        else
            rules.set(k, [v]);
    });

    const correctArray: Array<Array<number>> = [];
    const incorrectArray: Array<Array<number>> = [];

    content_input.split("\n").map(v => v.split(",").map(v => Number(v))).forEach(pages => {
        if(CheckPages(pages, rules)[0])
            correctArray.push(pages);
        else
            incorrectArray.push(pages);
    });

    const part_1 = correctArray.reduce<number>(ReduceMiddleNumbers, 0);
    const part_2 = incorrectArray.map((v) => Reposition([...v], rules)).reduce<number>(ReduceMiddleNumbers, 0);

    return {
        part_1,
        part_2,
    }
}

[โ€“] reboot6675@sopuli.xyz 1 points 2 weeks ago (1 children)

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)
}

load more comments (1 replies)
[โ€“] wer2@lemm.ee 1 points 2 weeks ago

Lisp

Part 1 and 2


(defun p1-process-rules (line)
  (mapcar #'parse-integer (uiop:split-string line :separator "|")))

(defun p1-process-pages (line)
  (mapcar #'parse-integer (uiop:split-string line :separator ",")))

(defun middle (pages)
  (nth (floor (length pages) 2) pages))

(defun check-rule-p (rule pages)
  (let ((p1 (position (car rule) pages))
        (p2 (position (cadr rule) pages)))
    (or (not p1) (not p2) (< p1 p2))))

(defun ordered-p (pages rules)
  (loop for r in rules
        unless (check-rule-p r pages)
          return nil
        finally
           (return t)))

(defun run-p1 (rules-file pages-file) 
  (let ((rules (read-file rules-file #'p1-process-rules))
        (pages (read-file pages-file #'p1-process-pages)))
    (loop for p in pages
          when (ordered-p p rules)
            sum (middle p)
          )))

(defun fix-pages (rules pages)
  (sort pages (lambda (p1 p2) (ordered-p (list p1 p2) rules)) ))

(defun run-p2 (rules-file pages-file) 
  (let ((rules (read-file rules-file #'p1-process-rules))
        (pages (read-file pages-file #'p1-process-pages)))
    (loop for p in pages
          unless (ordered-p p rules)
            sum (middle (fix-pages rules p))
          )))

load more comments
view more: โ€น prev next โ€บ