diff options
| -rw-r--r-- | 8.c | 124 | ||||
| -rw-r--r-- | makefile | 1 |
2 files changed, 125 insertions, 0 deletions
@@ -0,0 +1,124 @@ + +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + + +// Check if a tree is newly seen, by being taller than max or not +// +// If it is seen, update max. +// +// If the tree is seen, and has not been seen before, return 1 +// Otherwise return 0 +int +tree_seen(int * max, unsigned char * tree) +{ + int height = (*tree & 0x7F) - '0'; + int seen = 0; + + if (height > *max) { + if (!(*tree & 0x80u)) { + *tree |= 0x80u; + ++seen; + } + *max = height; + } + + return seen; +} + + +// Check the number of seen trees in a forest +int +forest_seen(unsigned char * forest, int rows, int cols) +{ + int i, j, max, seen = 0; + + // For each row... + for (i = 0; i < rows; ++i) { + // Check which trees can be newly seen from the left + for (j = 0, max = -1; j < cols - 1 && max < 9; ++j) { + seen += tree_seen(&max, forest + i * cols + j); + } + + // Check which trees can be newly seen from the right + for (j = cols - 2, max = -1; j >= 0 && max < 9; --j) { + seen += tree_seen(&max, forest + i * cols + j); + } + } + + // For each column... + for (j = 0; j < cols - 1; ++j) { + // Check which trees can be newly seen from the top + for (i = 0, max = -1; i < rows && max < 9; ++i) { + seen += tree_seen(&max, forest + i * cols + j); + } + + // Check which trees can be newly seen from the bottom + for (i = rows - 1, max = -1; i >= 0 && max < 9; --i) { + seen += tree_seen(&max, forest + i * cols + j); + } + } + + return seen; +} + + +int +main() +{ + int cols = 0, rows = 0; + char * forest; + + // Read first line + forest = malloc(BUFSIZ); + if (!fgets(forest, BUFSIZ, stdin)) { + fprintf(stderr, "Need more input!\n"); + return -1; + } + cols = strlen(forest); + if (cols < 2 || forest[cols - 1] != '\n') { + fprintf(stderr, "Unexpected first line! (length %d)\n", cols); + return -1; + } + ++rows; + + while (1) { + // Resize forest for next line. + // Do the dumb thing and rely on realloc() to overallocate and manage + // exponential growth of the underlying buffer + // + // If we were expecting huge input, we could just ask for a filename and + // mmap() it. + char * p = realloc(forest, (long) cols * (rows + 1) + 1); + if (!p) { + fprintf(stderr, "Realloc %ld fail! (%s)\n", + (long) cols * (rows + 1) + 2, strerror(errno)); + free(forest); + return -1; + } + forest = p; + + // Read line. + p = forest + cols * rows; + if (!fgets(p, cols + 1, stdin)) + break; + + // Check line length + if (strlen(p) != cols || p[cols - 1] != '\n') { + fprintf(stderr, "Unexpected line length for %s\n", p); + free(forest); + return -1; + } + + ++rows; + } + + printf("Trees seen: %d\n", forest_seen((unsigned char *) forest, rows, cols)); + + free(forest); + + return 0; +} + @@ -9,6 +9,7 @@ all: bin \ bin/5 \ bin/6 \ bin/7 \ + bin/8 \ bin: mkdir -p $@ |