2022 Day 3

Posted on Dec 3, 2022

Part 1

Problem

Each line in the file represents a rucksack, and each character of the line represents an item. Rucksacks have two compartments, with the items split evenly between them (first n / 2 items go in the first compartment, the rest in the second compartment).

General solution

Create a nested data structure which comprises of:

Rucksacks.
Rucksack compartments.
Contents of compartments.

We also need a list of priorities for each letter a..z and A..Z.

Solution: Go

For the list of priorities, Go unfortunately does not have an equivalent of the PHP range function, which would make building the priority list straightforward. Rather than try and work out an automated solution, we can simply hardcore a map of priorities as it only has 52 elements (we use a map because that allows us to quickly find the priority for a given letter). An alternative would be to find use the ASCII value of each letter plus or minus an offset, as letters are sequential in ASCII (i.e. the value for z will always be the value for a plus 25).

We need a simple data structure for rucksacks, which contain compartments, which in turn contain items.

We also define a compartment count, as we want to be able to increase the number of compartments, should this be required in Part 2 (and this makes the code clearer).

Converting the input into a slice of Rucksacks is fairly straightforward - we need to read in the input one line at a time and then convert each line into a slice of letters (technically these are UTF-8 sequences, however we know the input is effectively ASCII and therefore one sequence equals one letter). The only complexity here is dividing the slice into compartments, but fortunately Go supports indexing slices with [x:y] to return a subslice. We can easily calculate the size of each compartment as they are guaranteed to be equal, so it is simply a case of dividing the rucksack size by the number of compartments and then calculating offsets as required.

Once we have the rucksack data in our structure, we need to:

Iterate over each rucksack.
Within the rucksack, find the first compartment (it doesn’t matter which compartment we use, but the first makes sense).
For every letter within the first compartment, check if a match exists within all the other compartments.

The easiest way to check if a match exists within all the other compartments is to iterate over their contents and keep a count of how many times we find the same letter. If the letter count equals the compartment count, then by definition the letter must be in all of the compartments. However, if the same letter is present multiple times in a compartment it will inflate the count and result in an incorrect comparison, therefore we have to also check for duplicates to make sure a letter is only counted once.

Without this duplicate check, a solution will still return the correct answer (157) for the test input, however it may return an answer which is incorrect for the main input.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	const compartmentCount = 2

	type RucksackCompartment struct {
		contents []string
	}

	type Rucksack struct {
		compartments [compartmentCount]RucksackCompartment
	}

	// IMPROVEMENT: This could be generated dynamically
	priorities := map[string]int{
		"a": 1,
		"b": 2,
		"c": 3,
		"d": 4,
		"e": 5,
		"f": 6,
		"g": 7,
		"h": 8,
		"i": 9,
		"j": 10,
		"k": 11,
		"l": 12,
		"m": 13,
		"n": 14,
		"o": 15,
		"p": 16,
		"q": 17,
		"r": 18,
		"s": 19,
		"t": 20,
		"u": 21,
		"v": 22,
		"w": 23,
		"x": 24,
		"y": 25,
		"z": 26,
		"A": 27,
		"B": 28,
		"C": 29,
		"D": 30,
		"E": 31,
		"F": 32,
		"G": 33,
		"H": 34,
		"I": 35,
		"J": 36,
		"K": 37,
		"L": 38,
		"M": 39,
		"N": 40,
		"O": 41,
		"P": 42,
		"Q": 43,
		"R": 44,
		"S": 45,
		"T": 46,
		"U": 47,
		"V": 48,
		"W": 49,
		"X": 50,
		"Y": 51,
		"Z": 52,
	}

	rucksacks := []Rucksack{}

	scanner := bufio.NewScanner(os.Stdin)

	// Read in the data and convert into structure
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())
		items := strings.Split(line, "")
		compartmentSize := len(items) / compartmentCount

		rucksack := Rucksack{}

		// ASSUMPTION: Compartments are always the same size and contents are
		// evenly distributed between compartments
		for compartmentIndex := 0; compartmentIndex < compartmentCount; compartmentIndex++ {
			compartmentStart := compartmentIndex * compartmentSize
			compartmentEnd := compartmentStart + compartmentSize
			rucksack.compartments[compartmentIndex].contents = items[compartmentStart:compartmentEnd]
		}

		rucksacks = append(rucksacks, rucksack)
	}

	// Search all rucksacks to find common items in compartments
	prioritiesSum := 0

	for rucksackIndex := range rucksacks {
		rucksackCompartments := rucksacks[rucksackIndex].compartments
		firstCompartment := rucksackCompartments[0]

		// Keep a track of items seen as there may be duplicates, but we only
		// want to count an item once
		seenItems := make(map[string]bool)

		for firstCompartmentContentIndex := range firstCompartment.contents {
			// Check if this item exists in all other compartments
			firstCompartmentItem := firstCompartment.contents[firstCompartmentContentIndex]
			itemCount := 1

			_, seen := seenItems[firstCompartmentItem]

			if !seen {
				seenItems[firstCompartmentItem] = true

				for compartmentIndex := 1; compartmentIndex < compartmentCount; compartmentIndex++ {
					matchFound := false
					for compartmentContentIndex := range rucksackCompartments[compartmentIndex].contents {
						if !matchFound && rucksackCompartments[compartmentIndex].contents[compartmentContentIndex] == firstCompartmentItem {
							itemCount++
							matchFound = true
						}
					}
				}

				if itemCount == compartmentCount {
					prioritiesSum += priorities[firstCompartmentItem]
				}
			}
		}
	}

	fmt.Println(prioritiesSum)
}

Part 2

Problem

For each groups of three rucksacks, find the one item which is in all of the rucksacks.

General solution

Read all the rucksacks in again, except this time we can simplify the data structure by moving the contents up to the rucksack level and get rid of the compartments, because the lowest level of aggregation we need is the rucksack. As with Part 1, we need to make sure we only count an item once per rucksack, regardless of how many times it appears.

Solution: Go

We start off by eliminating the RucksackCompartment struct and moving the contents member up to the Rucksack struct. This simplifies the data structures as we no longer need to look inside compartments - we are instead looking at the rucksack as a whole.

The rest of the solution is similar to Part 1, but instead of iterating over compartments we iterate over rucksack groups (we could have created a RucksackGroup struct to represent these).

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	const rucksackGroupCount = 3

	type Rucksack struct {
		contents []string
	}

	// IMPROVEMENT: This could be generated dynamically
	priorities := map[string]int{
		"a": 1,
		"b": 2,
		"c": 3,
		"d": 4,
		"e": 5,
		"f": 6,
		"g": 7,
		"h": 8,
		"i": 9,
		"j": 10,
		"k": 11,
		"l": 12,
		"m": 13,
		"n": 14,
		"o": 15,
		"p": 16,
		"q": 17,
		"r": 18,
		"s": 19,
		"t": 20,
		"u": 21,
		"v": 22,
		"w": 23,
		"x": 24,
		"y": 25,
		"z": 26,
		"A": 27,
		"B": 28,
		"C": 29,
		"D": 30,
		"E": 31,
		"F": 32,
		"G": 33,
		"H": 34,
		"I": 35,
		"J": 36,
		"K": 37,
		"L": 38,
		"M": 39,
		"N": 40,
		"O": 41,
		"P": 42,
		"Q": 43,
		"R": 44,
		"S": 45,
		"T": 46,
		"U": 47,
		"V": 48,
		"W": 49,
		"X": 50,
		"Y": 51,
		"Z": 52,
	}

	rucksacks := []Rucksack{}

	scanner := bufio.NewScanner(os.Stdin)

	// Read in the data and convert into structure
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())

		rucksack := Rucksack{}
		rucksack.contents = strings.Split(line, "")

		rucksacks = append(rucksacks, rucksack)
	}

	// Search every group of 3 rucksacks to find the one common item
	prioritiesSum := 0

	for rucksackIndex := 0; rucksackIndex < len(rucksacks); rucksackIndex += rucksackGroupCount {
		firstRucksack := rucksacks[rucksackIndex]

		// Keep a track of items seen as there may be duplicates, but we only
		// want to count an item once
		seenItems := make(map[string]bool)

		for firstRucksackContentIndex := range firstRucksack.contents {
			// Check if this item exists in all other rucksacks in this group
			firstRucksackItem := firstRucksack.contents[firstRucksackContentIndex]
			itemCount := 1

			_, seen := seenItems[firstRucksackItem]

			if !seen {
				seenItems[firstRucksackItem] = true

				for rucksackGroupIndex := rucksackIndex + 1; rucksackGroupIndex < rucksackIndex+rucksackGroupCount; rucksackGroupIndex++ {
					matchFound := false
					for rucksackContentIndex := range rucksacks[rucksackGroupIndex].contents {
						if !matchFound && rucksacks[rucksackGroupIndex].contents[rucksackContentIndex] == firstRucksackItem {
							itemCount++
							matchFound = true
						}
					}
				}

				if itemCount == rucksackGroupCount {
					prioritiesSum += priorities[firstRucksackItem]
				}
			}
		}
	}

	fmt.Println(prioritiesSum)
}

Post-solution thoughts

A RucksackGroup struct may have made the code clearer in Part 2. The trade-off involved was:

No rucksack grouping: The code for reading the input is simpler, but the code for processing the data structure has to group rucksacks on the fly.

Rucksack grouping: The code for reading the input is more complex, but the code for processing the data structure can iterate directly over rucksack groups without having to calculate offsets.

As a general rule though, simplicity in reading input is to be preferred, as the most important thing is to get the input into some form of data structure - after which it can be processed, printed, debugged etc.