Day 5: Print Queue
Part 1
This task requires us to parse the provided input and seperate it into rules and the updates.
For this I used the following:
function parseInput(input: string) {
return input.trim().split('\n\n');
}
I then parse the rules into a dictionary, this will allow quick access to each update's rule by using it as the key.
function buildRules(ruleString: string) {
const ruleDict: { [before: string]: [after: number] } = {};
ruleString.split('\n').forEach(function (rule) {
const [before, after] = rule.split('|').map(Number);
if (ruleDict.hasOwnProperty(before)) {
ruleDict[before].push(after);
}
else {
ruleDict[before] = [after];
}
});
return ruleDict;
}
To the main part of the task, we need to check each update in order and see if their pages are following the rules, if they are not we exclude them from our return. Below is my approach.
function checkIfInOrder(updateString: string, rules: Record<number, number[]>): number[][] {
const updates: number[][] = [];
const lines = updateString.split('\n').map(line => line.split(',').map(Number));
for (const line of lines) {
let valid = true;
const seen = new Set<number>();
for (const page of line) {
const afterNumbers = rules[page] || [];
for (const prevPage of seen) {
if (afterNumbers.includes(prevPage)) {
valid = false;
break;
}
}
if (!valid) break;
seen.add(page);
}
if (valid) updates.push(line);
}
return updates;
}
I take in as parameters, the updateString and the already parsed rules. I then split the string into lines, and further into an array of numbers by splitting on commas.
Next I iterate over each line, defining a variable of valid to true. I also create a set to keep track of the numbers we have already seen.
Next, iterating over each page within line, I access my rules for each page, pulling the numbers which the rules define should appear after. Then for each number within the set aka each number that has appeared already within this line, if one of them is present in the afterNumbers we break as this is an invalid line.
Otherwise, the current page is added to the set. This function then returns only the lines that are valid.
Finally, for each valid line, I take the middle value and add this to a running total to get the part 1 result.
function calculateTotal(reorderedUpdates: number[][]) {
let total = 0;
for (let i = 0; i < reorderedUpdates.length; i++) {
const middleIndex = Math.floor(reorderedUpdates[i].length / 2);
total += reorderedUpdates[i][middleIndex];
}
return total;
}
const [ruleString, updateString] = parseInput(input);
const rules = buildRules(ruleString);
const validUpdates = checkIfInOrder(updateString, rules);
const total = calculateTotal(validUpdates);
Part 2
For part 2, I take advantage of my existing part 1 code, inverting the criteria (finding invalid instead of valid) to then re-order these found lines before returning them for the total calculation.
function checkIfInOrder(updateString: string, rules: {}) {
const updates: number[][] = [];
const lines = updateString.split('\n').map(line => line.split(',').map(Number));
for (const line of lines) {
let valid = true;
const seen = new Set < number > ();
for (const page of line) {
const afterNumbers = rules[page] || [];
for (const prevPage of seen) {
if (afterNumbers.includes(prevPage)) {
valid = false;
break;
}
}
if (!valid) break;
seen.add(page);
}
// Part 1 re-used end
With my part 1 code reused, I then added a check for if valid is false. This would signal that re-ordering is needed.
if (!valid) {
// reorder
const reorderedLine = [];
for (let pageIndex = 0; pageIndex < line.length; pageIndex++) {
const currentPage = line[pageIndex];
reorderedLine.push(currentPage);
let lastPageIndex = pageIndex - 1;
if (rules[currentPage]) {
while (lastPageIndex >= 0 && rules[currentPage].includes(reorderedLine[lastPageIndex])) {
const temp: number = reorderedLine[lastPageIndex + 1];
reorderedLine[lastPageIndex + 1] = reorderedLine[lastPageIndex];
reorderedLine[lastPageIndex] = temp;
lastPageIndex = lastPageIndex - 1;
}
}
}
updates.push(reorderedLine);
}
This code declares a new array called reorderedLine. I then iterate of the current line to get each page.
The current page is then added to the reorderedLine array.
I also at this point get the index of the previous page.
Then whilst rules exist for the page we are currently one, a while loop is used. This loop will continue whilst lastPageIndex is greater or equal to zero, this ensures that it will hit each page before our current. The loop is also continuing whilst there is a rule breach for our current page, i.e. a page before our current page, should be positioned behind.
Within the loop I am then simply swapping the pages positions in order based on the current lastPageIndex.
This results with a perfectly sorted updates list based on the rules provided. This list is then returned alongside all the other invalid update lists for total calculation in order to get the final result.
Full function.
function checkIfInOrder(updateString: string, rules: {}) {
const updates: number[][] = [];
const lines = updateString.split('\n').map(line => line.split(',').map(Number));
for (const line of lines) {
let valid = true;
const seen = new Set<number>();
for (const page of line) {
const afterNumbers = rules[page] || [];
for (const prevPage of seen) {
if (afterNumbers.includes(prevPage)) {
valid = false;
break;
}
}
if (!valid) break;
seen.add(page);
}
if (!valid) {
// reorder
const reorderedLine = [];
for (let pageIndex = 0; pageIndex < line.length; pageIndex++) {
const currentPage = line[pageIndex];
reorderedLine.push(currentPage);
let lastPageIndex = pageIndex - 1;
if (rules[currentPage]) {
while (lastPageIndex >= 0 && rules[currentPage].includes(reorderedLine[lastPageIndex])) {
const temp: number = reorderedLine[lastPageIndex + 1];
reorderedLine[lastPageIndex + 1] = reorderedLine[lastPageIndex];
reorderedLine[lastPageIndex] = temp;
lastPageIndex = lastPageIndex - 1;
}
}
}
updates.push(reorderedLine);
}
}
return updates;
}
Total calculation (Same as part 1)
function calculateTotal(reorderedUpdates: number[][]) {
let total = 0;
for (let i = 0; i < reorderedUpdates.length; i++) {
const middleIndex = Math.floor(reorderedUpdates[i].length / 2);
total += reorderedUpdates[i][middleIndex]; }
return total;
}
const [ruleString, updateString] = parseInput(input2);
const rules: {} = buildRules(ruleString);
const validUpdates = checkIfInOrder(updateString, rules);
const total = calculateTotal(validUpdates);