Day 2: Red-Nosed Reports
Part 1
Today's task consists of processing many reports. Each report contains a string of numbers called levels, separated by spaces.
Such as the below:
7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9
The task is to figure out which reports are safe. The conditions for this is the following:
- Within a report, the levels are either all increasing or all decreasing.
- Within a report, any two adjacent levels differ by at least one and at most three
Both conditions which must be met for a report to be classed as safe.
To begin I start in a similar fashion to "Day One", copying the input string into my project and first parsing it into an array of arrays.
function make_report_array(input: string) {
const reports = input.trim().split('\n');
// regex to match levels
const regex = /\d+/g;
// return the parsed reports reusing "Day 1" regex and parseInt
return reports.map((report) => {
const matches = report.match(regex);
if (matches) {
return matches.map(level => parseInt(level, 10));
}
return [];
});
}
This provides me with the following:
const parsed_reports = make_report_array(reports);
// parsed_reports example
[
[7, 6, 4, 2, 1],
[1, 2, 7, 8, 9],
[9, 7, 6, 2, 1],
[1, 3, 2, 4, 5],
[8, 6, 4, 4, 1],
[1, 3, 6, 7, 9]
]
With this I can now check each report and see if they are safe.
A trick here is to recognise that one condition is asking if the reports are monotonic. Monotonic Functions Wikipedia
With this in mind, instead of focusing on if the array is increasing or otherwise decreasing, we can instead focus on determining if it is monotonic, i.e. all increasing or all decreasing.
Below is my function to check each report:
function check_if_monotonic(report: Array<number>) {
let decreasing = true;
let increasing = true;
// start at index 1 to allow us to check the previous index
for (let i = 1; i < report.length; i++) {
// define variables for comparisons
const current = report[i];
const previous = report[i - 1];
// if true, this means the array is not decreasing
if (current > previous) {
decreasing = false;
}
// if true, this means the array is not increasing
if (current < previous) {
increasing = false;
}
}
// if both are false then it is not monotonic, if only 1 is false then we know it is
return decreasing || increasing;
}
This function runs through each level, comparing it to the previous level. It will then set decreasing or increasing to false depending on the values compared, resulting with either both false (not monotonic) or one false (monotonic). It's also worth noting arrays that are empty or have a length one are also monotonic.
With check 1 complete we can then check the adjacency requirement. Below is my implementation:
function check_adjacents(report: Array<number>) {
let valid = true;
for (let i = 1; i < report.length; i++) {
const current = report[i];
const previous = report[i - 1];
// check if the difference between the current and previous is between 1 and 3
if (Math.abs(current - previous) > 3 || Math.abs(current - previous) < 1) {
valid = false;
}
}
// return the status of valid, which will be false if the check failed
return valid;
}
This function is rather simple and just checks to see if the adjacent values fall within the 1 to 3 distance that is required. It could also benefit from returning early when valid is set to false in order to avoid extra processing.
Finally, I create a quick function to run both my checks before looping on parsed_reports.
It is also worth noting that my two conditional functions can be combined into a single loop in order to improve time complexity, but for clarity I have left them implemented separately (Please see below for the combined function).
function is_report_safe(report: Array<number>) {
return check_if_monotonic(report) && check_adjacents(report);
}
let total = 0
for (let i = 0; i < parsed_reports.length; i++) {
if (is_report_safe(parsed_reports[i])) {
total++;
}
}
This provided me with the correct result.
Part 2
Part 2 introduces a change into our criteria of a safe level, in that a report can be considered safe if it passes when one bad level is removed.
To begin I will separate my good and bad reports as there is no need to check those already considered safe. This can be done easily by adjusting my code to the following:
let total = 0;
const unsafe = [];
for (let i = 0; i < parsed_reports.length; i++) {
if (check_if_monotonic(parsed_reports[i]) && check_adjacents(parsed_reports[i])) {
total++;
}
else {
unsafe.push(parsed_reports[i]);
}
}
It is here that I chose to loop through each report, and run them through my "check_with_dampener" function. This function will remove each level in turn and see if the report qualifies as safe. If there is a safe variation then it will return true.
let total_dampened = 0;
for (let i = 0; i < unsafe.length; i++) {
if (check_with_dampener(unsafe[i])) {
total_dampened++;
}
}
function check_with_dampener(report: Array<number>) {
for (let i = 0; i < report.length; i++) {
if (is_report_safe(report.toSpliced(i, 1))) {
return true;
}
}
return false;
}
To then get the final amount of safe reports I add total_dampened to total.
Combined function for improving time complexity
function is_report_safe(report: Array<number>){
let decreasing = true;
let increasing = true;
for (let i = 1; i < report.length; i++) {
const current = report[i];
const previous = report[i - 1];
const diff = Math.abs(current - previous);
// monotonic check
if (current > previous) {
decreasing = false;
}
if (current < previous) {
increasing = false;
}
// adjacent differences
if (diff < 1 || diff > 3) {
return false;
}
}
return decreasing || increasing;
}