Advent of Code Day 5 in Golang: Ordering Pages
Introduction
It is day 5 of the advent of code, and today we have an interesting problem of ordering pages. Let’s dive into the problem and how I approached it. It was a pretty simple problem if thought it peacefully, otherwise, it would get into a map, list, and indices mess.
Input
In the input for day 5, we have two sections, The first defines the rules for ordering the pages, specifically which page should come before which and the second contains the actual order of pages.
47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13
75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47
So, the first section has the rules mapped out, the other has the ordering of pages, and each line is a query or a list of pages as our actual data to process. We need to use it in the processing of parts 1 and 2.
Reading Sections
So, we need to parse these sections and read them in a data structure that could be easier to access.
One way to do that would be
A list with two sections
The first section will be a list
- The list will be a list of integers to hold the two integers i.e. for rules
The second section will be a list
- The list will be a list of integers to hold the page list
So, the data structure would look like a list of list of list of integers.
func ReadFileSections(path string) [][][]int {
fileBytes := ReadFileBytes(path)
lines := []string{}
separator := []byte("\n\n")
for _, line := range bytes.Split(fileBytes, separator) {
if string(line) != "" {
lines = append(lines, string(line))
}
}
sections := [][][]int{}
for i, section := range lines {
nums := [][]int{}
lineStrs := strings.Split(section, "\n")
separator := ","
if i == 0 {
separator = "|"
}
for _, lineStr := range lineStrs {
if lineStr == "" {
continue
}
numL := []int{}
for _, numStr := range strings.Split(lineStr, separator) {
num, _ := strconv.Atoi(numStr)
numL = append(numL, num)
}
nums = append(nums, numL)
}
sections = append(sections, nums)
}
return sections
}
The above function called ReadFileSections takes in a path to the input file and returns a slice/array) of the list of list of integers as discussed. We first read the file and split the bytes into two newline characters that will be the separator for the sections, we will store the lines as a list of strings, the first will contain the rule lines and the second will contain the page list lines.
Then we iterate over the section and split the individual lines for sections separately with the respective separator i.e. | for the first section and (whitespace) for the second section. We are parsing each line to get a list of integers and append them to the respective sections.
So, we now have data that we can use to construct the rules and pages to help process the problem.
Constructing Rules
Now, we need to process the rules list for convenient access, we need to get the page number that should appear after a given page, so we will use a map of integer with a list of integers, where the key will be the first number and the one of the value will be the second number ( the number that should appear after in order of the pages).
func ConstructRules(rulesList [][]int) map[int][]int {
rules := make(map[int][]int)
for _, rule := range rulesList {
rules[rule[0]] = append(rules[rule[0]], rule[1])
}
return rules
}
We simply iterate over the list of integers and map the first element as the key and the value as the second element in the list, so to visualize:
FROM
[][]int
[
[47,53]
[97,13]
[97,61]
]
TO
map[int][]int
{
47: [53]
97: [13,61]
}
So, now have the rules as a map of integers with integers.
Constructing indices
Now, to make the first and second parts easier, we need to make a map for each number in the rules section with the indices that appear in the pages list.
So, we will iterate over the rules, which is a map of integers and integers, we will create a map of integers that will help us create a unique list of integers from the rules.
Now, once we have the list of integers from the rules, we will iterate over all the numbers and on each page line, check on which index it appears, for creating a list of integers(indices).
So, we iterate over all the numbers in the line of pages, if we find that number in the list of pages, we append the index, however, if we don’t we append -1, so for each line we need to have an index appended for that number like so:
# 75
75,47,61,53,29 -> 0
97,61,53,29,13 -> -1
75,29,13 -> 0
75,97,47,61,53 -> 0
61,13,29 -> -1
97,13,75,29,47 -> 2
75[0,-1,0,0,-1,2]
# map[int][]int
# 75 -> int
# [0,-1,0,0,-1,2] -> []int
So, in the above example, we have taken 75 for reference, we will get the index for each list of page numbers, and we get the list of indexes where 75 appears.
Now, this can be done with the following function:
func GetPageIndices(rules map[int][]int, pages [][]int) map[int][]int {
nums := make(map[int]bool)
for num, list := range rules {
nums[num] = true
for _, elem := range list {
if !nums[elem] {
nums[elem] = true
}
}
}
numIndices := make(map[int][]int)
for num, _ := range nums {
for _, numLine := range pages {
index := -1
for i, n := range numLine {
if n == num {
index = i
}
}
numIndices[num] = append(numIndices[num], index)
}
}
return numIndices
}
So, we now have the index mapped at each page numbers list from the rules.
Part 1
Now, for part one we need to iterate over each page update (line), then we need to check if the page numbers are following the rules, each number should follow the rules. This means that if a number is after a certain number but the rule says it should be before, then it has violated the page numbering rule in that update, so we cannot consider it as the correct ordered page, we need to add the middle page number of each update which is correctly ordered as the answer for the part one.
To do that, we iterate over each page update, then we need to iterate over each of the numbers in that page update, we obtain all the rules associated with that number (let’s call it the current number) since we have a map of integers with a list of integers. Now, we have to check if the number that we currently are in is before the numbers in its rules. So, we check with the index of the current number using the number indices that we created which is a map of the number with a list of integers as indices. So, we obtain the list of indices of the map with the current number as the key for the map and the index in the list as the number of line/page updates we are currently in.
Then once we have got the index for the current number, we obtain the same for the second number which is all the numbers in its rule, and if that number in its rule is present in that page line/update i.e. it is not -1 and if that is the case, we get the index of it similarly and check if it appears after the current number following the rule, And so if any number violates the rule, we need to mark the page update as not in correct order.
As we see that the index rule for that page update is violated, we mark the order as false. If we see the ordered flag is still true, we update the score with the middle element of that page update.
func GetOrderedPages(rules, numIndices map[int][]int, pages [][]int) int {
score := 0
for index, pageLine := range pages {
ordered := true
for _, num1 := range pageLine {
rule := rules[num1]
index1 := numIndices[num1][index]
for _, num2 := range rule {
index2 := numIndices[num2][index]
if index1 == -1 || index2 == -1 {
continue
}
if index1 > index2 {
ordered = false
}
}
}
if ordered {
score += pageLine[int(len(pageLine)/2)]
}
}
return score
}
So, to reiterate, we create a function called GetOrderedPage with rule and number indices as a map of integers with a list of integers and the pages which is a list of integers as the page update. We return the score as the output of this function.
We iterate through each of the page updates, then through each page number in the update, we check for the rule of that number and if the index of that is lower than the current number we mark it as not ordered, and hence at the end of each page update we update the score with the middle element of the page update, if the order is correct.
So, that will be part one summed up, we just have to get the score of the correct ordered page updates.
Part 2
In part 2 however, we need to check if the page update is in order, if it is not then we need to make it in order.
We do a similar thing for part 2, we need to iterate over each of the page updates, and for each number in that page update, we need to check if the rule is violated or not, if we encounter any case where the rule is violated for any number, we mark the flag ordered as false, this we will use to correct the order of the page updates. After updating the pages in that page line/update, we need to add the score with middle element of the corrected order of page update.
func GetCorrectOrderedPages(rules, numIndices map[int][]int, pages [][]int) int {
score := 0
for index, pageLine := range pages {
ordered := true
for _, num1 := range pageLine {
rule := rules[num1]
index1 := numIndices[num1][index]
for _, num2 := range rule {
index2 := numIndices[num2][index]
if index1 == -1 || index2 == -1 {
continue
}
if index1 > index2 {
ordered = false
}
}
}
if !ordered {
newLine := CorrectPageOrder(pageLine, rules)
score += newLine[len(newLine)/2]
}
}
return score
}
We need to implement the CorrectPageOrder function that takes in the page line or page update and the rules, we need to create a new page update, that will populate the page that follows all the rules.
So, we first keep track of the initialized elements index and update the index if we need to move the element before it.
So, we iterate over all the numbers in the page update and set the index before any number in the rule, if we encounter any such number in the rule map, we need to update the index with the index of that number.
And once we have got the index where we want to swap the element to, we create a slice before that index and append that number into it, and append everything after that index.
func CorrectPageOrder(line []int, rules map[int][]int) []int {
newLine := []int{}
for _, num := range line {
index := make(map[int]int)
for i, n := range newLine {
index[n] = i
}
newInsertIndex := len(newLine)
for _, rule := range rules[num] {
if idx, ok := index[rule]; ok {
if newInsertIndex > idx {
newInsertIndex = idx
}
}
}
afterNum := slices.Clone(newLine[newInsertIndex:])
newLine = append(newLine[:newInsertIndex], num)
newLine = append(newLine, afterNum...)
}
return newLine
}
So, this function will find the index of a number to place it at the most extreme left (beginning of the list) so that we are not violating any rules for that number, then we create a slice to append that number before that index and append everything after that index.
That’s it from part two, we have updated the page order if there were any discrepancies in the page order.
Conclusion
So, that is it from day 5 of Advent of Code in Golang, let me know if you have any suggestions, and how you approached it. any better solutions?
Happy Coding :)