For day 2's puzzles, I'll be using plain old C, because who doesn't like bookkeeping?
For this task, we receive a series of lines ("reports"), each with space-separated integers. We want to count the number of lines for which all numbers are either increasing or decreasing, and for which all adjacent integers are have a difference of at least one and no more than three.
We can implement this by reading the first integer and storing it; we'll update this so that it always holds the previous value. Then we can read the second integer and note whether it's higher or lower than the first one. Finally, we can read each number in the line and ensure it's moving in the correct direction and in the appropriate range.
We can check report safety with a predicate the accepts the report as a string. Then we can use strtol to parse out the integers, and return false when we find something unsafe. If we reach the end of the report without finding enough data to process, we return false, so that eg blank lines will not be counted in the result; otherwise, reaching the end of the line means the report is safe, so we return true:
bool is_report_safe(const char *report)
{
const char *token = report;
char *next_token;
int previous_value = strtol(token, &next_token, 10);
token = next_token;
bool ascending = true;
for (
int value = strtol(token, &next_token, 10), i = 0;
*token != '\0';
value = strtol(token, &next_token, 10), ++i
) {
// If we reach the end before we have enough elements to
// process, ensure it isn't counted so that things like blank
// lines are ignored. Otherwise, if we reach the end of the
// line without finding anything unsafe, the report is safe.
if (token == next_token) return i > 0;
if (i == 0) ascending = previous_value < value;
int difference = abs(value - previous_value);
int unsafe = (
difference < 1 || difference > 3 ||
ascending && previous_value > value ||
!ascending && previous_value < value
);
if (unsafe) return false;
token = next_token;
previous_value = value;
}
return true;
}
To read the file into lines, we'll rely on the standard getline function, which handles allocating and reallocating a buffer for us. We'll loop over each line and increment a counter if it's safe, then clean up the file pointer and life buffer, and finally return the count of safe reports:
int count_safe_reports(const char *filename)
{
FILE *file = fopen(filename, "r");
if (file == NULL) {
perror("Error opening file");
exit(1);
}
int num_safe = 0;
char *report = NULL;
size_t len = 0;
while (getline(&report, &len, file) != -1) {
if (is_report_safe(report)) ++num_safe;
}
free(report);
fclose(file);
return num_safe;
}
Now we just need to call the function:
int main(void)
{
printf("%d\n", count_safe_reports("input.txt"));
}
For the second task, we need to modify the safety-checking so that a report is safe if, by optionally removing one element, we can make it safe according to the old rules.
For most of the list, this could be very easily handled by just continueing on the first unsafe element and waiting for a second to appear before we return false. Because of the ascending/descending and range requirements, there isn't much choice about which element to remove. Some safe reports could be missed by this approach, though, if the element to be removed is either the first or second element:
10 4 3 2 1 is safe by removing the 10, but if we remove the first unsafe element, the 4, then all the remaining elements will also be considered unsafe because they're still out of range.6 7 3 2 1 is safe by removing the 7 that establishes the report as descending, whereas if we remove the first unsafe element, the 3, the remaining elements will still be descending.Because there are only 4 cases, one way to check for all of them is to simply check for all of them. We could keep track of the different variants at once, verifying them all in one traversal, but this would introduce more bookkeeping than I'd like to deal with. A simpler approach is to just check the entire report repeatedly this is O(n) with a constant factor, so still O(n). We can rename is_report_safe to is_report_safe_aux and write a new is_report_safe function that just calls is_report_safe_aux 3 times with different parameters. We'll add parameters for the index to ignore (which can be 0, 1, or, if we don't want to ignore anything, -1) and the number of unsafe integers we're allowed to skip:
bool is_report_safe_aux(const char *report, int skips_allowed, int ignore_index);
bool is_report_safe(const char *report)
{
return (
is_report_safe_aux(report, 1, -1) ||
is_report_safe_aux(report, 0, 0) ||
is_report_safe_aux(report, 0, 1)
);
}
bool is_report_safe_aux(const char *report, int skips_allowed, int ignore_index)
{
const char *token = report;
char *next_token;
int previous_value;
bool ascending = true;
for (
int value = strtol(token, &next_token, 10), i = 0;
*token != '\0';
value = strtol(token, &next_token, 10), ++i
) {
// If we reach the end before we have enough elements to
// process, ensure it isn't counted so that things like blank
// lines are ignored. Otherwise, if we reach the end of the
// line without finding anything unsafe, the report is safe.
if (token == next_token) return i > 0;
// Initialize values on first unignored iteration.
if (i == 0 || ignore_index == 0 && i == 1) {
previous_value = value;
token = next_token;
value = strtol(token, &next_token, 10);
}
if (i == ignore_index) continue;
if (i == 1 || ignore_index >= 0 && i == 2) {
ascending = previous_value < value;
}
int difference = abs(value - previous_value);
int unsafe = (
difference < 1 || difference > 3 ||
ascending && previous_value > value ||
!ascending && previous_value < value
);
if (unsafe && skips_allowed > 0) --skips_allowed;
else if (unsafe) return false;
token = next_token;
previous_value = value;
}
return true;
}
This works, but apparently gives the wrong answer; mine is too high. I wonder if I was overthinking it about the first two characters being special cases?
bool is_report_safe(const char *report)
{
return is_report_safe_aux(report, 1, -1);
}
Yep, I was overthinking it.