Day 1: Historian Hysteria
Part 1
Part 1 of today's task requires me to format my input into a usable structure, as it currently consists of two lists contained within a single string.
To begin I initialised the string within JavaScript as follows:
const input = `aaaaa bbbbb
ccccc ddddd
eeeee fffff`
This allows for easy access as opposed to dealing with text files.
Next, I then created the following function:
function make_lists(input: string) {
// Make two empty arrays to store the left and right numbers
const leftList: number[] = [];
const rightList: number[] = [];
// Split the input string into individual lines
const lines = input.trim().split('\n');
// Regular expression to extract digits
const regex = /\d+/g;
// Process each line
for (let i = 0; i < lines.length; i++) {
// Find matches whilst also converting matches to integers
const matches = lines[i].match(regex)?.map(string => parseInt(string, 10));
// Store matches
leftList.push(matches[0]);
rightList.push(matches[1]);
}
// To avoid having to search for each smallest number, it is easiest to sort them
// We can then move down them index by index
return [leftList.sort(), rightList.sort()];
}
The make_lists function processes the input string, extracting numerical values and organising them into two sorted arrays. It begins by first creating two blank arrays where the results will be stored. I then trim and split the input string on newline characters. This makes an iterable array called "lines".
I also declare some regex that will grab the groups of digits within each line.
Then for each "line" within "lines", I grab the matching digit groups and convert them to be integers in order to assist me later before pushing them to the result arrays made earlier.
Finally, I return the data, but not before I sorted the two lists in numerical order.
This can then be ran with the following:
const [left, right] = make_lists(input);
Next, I work to create a function that will be able to calculate the distances between each list, and in my case store this as an array of distances.
function calculate_distances(left, right) {
const total = [];
for (let i = 0; i < left.length; i++) {
// Calculate the absolute difference and add to total
total.push(Math.abs(left[i] - right[i]));
}
return total;
}
This function takes in both of my lists and performs the distance calculation before pushing the result to the "total" array.
const total = calculate_distances(left, right);
Finally, I calculate the total distance by using a reduce accumulator.
const final_total = total.reduce((acc, current) => acc + current);
Part 2
Part 2 requires us to figure out exactly how often each number from the left list appears in the right list. We then must calculate a total similarity score.
For each item in the left list, its score is its value multiplied by its frequency within the right list.
As we are dealing with frequencies my go-to approach is to create a frequency map. With a frequency map we can then run down the left list and find its frequency immediately as opposed to conducting a list search using .filter.
// Function to calculate similarity score based on frequency
function list_similarity(left, right) {list
// Create a map to store the frequency of each number in the right list
const rightCounts = new Map<number, number>();
// Populate the frequency map
for (const value of right) {
rightCounts.set(value, (rightCounts.get(value) || 0) + 1);
}
// Now calculate the similarity score
let score = 0;
for (const value of left) {
// Retrieve the frequency from the map. Using 0 if not found
score += value * rightCounts.get(value) || 0;
}
return score;
}
This can then be run using the below to get the final result.
list_similarity(left, right);