commit 72036c6737f5a82db7241c7717d816e9e37a90d0
parent f05cd011db346762afadfe389af60d32c7b46172
Author: bsandro <email@bsandro.tech>
Date: Tue, 9 Dec 2025 17:53:54 +0200
day09 p1 works, p2 does not
Diffstat:
| A | day09.c | | | 247 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 247 insertions(+), 0 deletions(-)
diff --git a/day09.c b/day09.c
@@ -0,0 +1,247 @@
+#define _GNU_SOURCE
+#define __USE_GNU 1
+#include <errno.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <inttypes.h>
+#include <stdlib.h>
+#include <math.h>
+#include <stdbool.h>
+#include <string.h>
+#include "cputime.h"
+
+#define MAX(a,b) (((a)>(b))?(a):(b))
+#define MIN(a,b) (((a)<(b))?(a):(b))
+
+#define MAX_POINTS 500
+
+typedef union {
+ struct { int x, y; };
+ int n[2];
+} Point;
+
+typedef struct {
+ Point p1;
+ Point p2;
+} Line;
+
+static int64_t square(Point p1, Point p2) {
+ return llabs((p1.x-p2.x)+1) * llabs((p1.y-p2.y)+1);
+}
+
+static int btoi(int bufl, int buf[bufl]) {
+ int num = 0;
+ for (int i=0;i<bufl;++i) num = num*10+buf[i];
+ return num;
+}
+
+static int cmp_int64(const void *vi1, const void *vi2) {
+ int64_t r = *(const int64_t *)vi2 - *(const int64_t *)vi1;
+ if (r>0) return 1;
+ if (r<0) return -1;
+ return 0;
+}
+
+static bool square_has_points(int points_l, Point points[points_l], Point p1, Point p2) {
+ int minx = MIN(p1.x, p2.x);
+ int miny = MIN(p1.y, p2.y);
+ int maxx = MAX(p1.x, p2.x);
+ int maxy = MAX(p1.y, p2.y);
+ for (int i=0;i<points_l;++i) {
+ Point p = points[i];
+ if (p.x<maxx&&p.x>minx&&p.y<maxy&&p.y>miny) return true;
+ }
+ return false;
+}
+
+static bool lines_have_point(int lines_l, Line lines[lines_l], Point p) {
+ for (int i=0;i<lines_l;++i) {
+ Point p1 = lines[i].p1;
+ Point p2 = lines[i].p2;
+ if (p1.x==p2.x&&p1.x==p.x) { // vertical lines only
+ int miny = MIN(p1.y, p2.y);
+ int maxy = MAX(p1.y, p2.y);
+ if (p.y>=miny&&p.y<=maxy) return true;
+ }
+ }
+ return false;
+}
+
+static bool __attribute__((unused)) lines_have_point1(int lines_l, Line lines[lines_l], Point p) {
+ for (int i=0;i<lines_l;++i) {
+ Point p1 = lines[i].p1;
+ Point p2 = lines[i].p2;
+ if (p1.x==p2.x&&p1.x==p.x) {
+ int miny = MIN(p1.y, p2.y);
+ int maxy = MAX(p1.y, p2.y);
+ if (p.y>=miny&&p.y<=maxy) return true;
+ }
+ if (p1.y==p2.y&&p1.y==p.y) {
+ int minx = MIN(p1.x, p2.x);
+ int maxx = MAX(p1.x, p2.x);
+ if (p.x>=minx&&p.x<=maxx) return true;
+ }
+ }
+ return false;
+}
+
+static bool point_is_inside(int lines_l, Line lines[lines_l], int maxx, Point p) {
+ //printf("check point %d:%d...\n", p.x,p.y);
+ int num = 0;
+ for (;p.x<=maxx+1;p.x++) {
+ if (lines_have_point(lines_l, lines, p)) {
+ num++;
+ //printf("%d:%d is on lines\n", p.x,p.y);
+ }
+ }
+ //printf("%d:%d intersections: %d (%d)\n",p.x,p.y,num,num%2==1);
+ return num%2==1;
+}
+
+static bool square_valid(int lines_l, Line lines[lines_l], int maxx, Point p1, Point p2) {
+ Point p3 = (Point){ .x=p1.x, .y=p2.y };
+ Point p4 = (Point){ .x=p2.x, .y=p1.y };
+ return (point_is_inside(lines_l, lines, maxx, p3) && point_is_inside(lines_l, lines, maxx, p4));
+}
+
+static int get_max_x(int points_l, Point points[points_l]) {
+ int maxx = 0;
+ for (int i=0;i<points_l;++i) {
+ if (points[i].x>maxx) maxx=points[i].x;
+ }
+ return maxx;
+}
+
+void gen_pbm(int lines_l, Line lines[lines_l]) {
+ Point min = {0};
+ Point max = {0};
+ for (int i=0;i<lines_l;++i) {
+ if (lines[i].p1.x<min.x) min.x=lines[i].p1.x;
+ if (lines[i].p2.x<min.x) min.x=lines[i].p2.x;
+ if (lines[i].p1.y<min.y) min.y=lines[i].p1.y;
+ if (lines[i].p2.y<min.y) min.y=lines[i].p2.y;
+ if (lines[i].p1.x>max.x) max.x=lines[i].p1.x;
+ if (lines[i].p2.x>max.x) max.x=lines[i].p2.x;
+ if (lines[i].p1.y>max.y) max.y=lines[i].p1.y;
+ if (lines[i].p2.y>max.y) max.y=lines[i].p2.y;
+ }
+ int w = max.x+3; //-min.x;
+ int h = max.y+3; //-min.y;
+ printf("%dx%d\n",w,h);
+ int f = open("day09.pbm", O_CREAT | O_WRONLY | O_TRUNC, 0666);
+ //fcntl(f, F_NOCACHE, 1);
+ char header[64] = {0};
+ int n = snprintf(header, sizeof(header), "P1\n%d %d\n", w, h);
+ if (write(f, header, n)!=n) {
+ printf("error: %d\n", errno);
+ exit(1);
+ }
+ puts("header write ok");
+ size_t len = sizeof(char)*w*h;
+ printf("size: %zu\n", len);
+ char *pic = malloc(len);
+ if (pic==NULL) { printf("error: %d\n", errno); exit(1); }
+ memset(pic, '0', len);
+ puts("malloc ok");
+ for (int i=0;i<lines_l;++i) {
+ Point p1 = lines[i].p1;
+ Point p2 = lines[i].p2;
+ if (p1.x==p2.x) {
+ int miny = MIN(p1.y, p2.y);
+ int maxy = MAX(p1.y, p2.y);
+ for (int y=miny;y<=maxy;++y) {
+ size_t offset = (size_t)y*w + p1.x;
+ if (offset>=len) { printf("invalid offset y %zu\n", offset); exit(1); }
+ pic[offset] = '1';
+ }
+ } else if (p1.y==p2.y) {
+ int minx = MIN(p1.x, p2.x);
+ int maxx = MAX(p1.x, p2.x);
+ for (int x=minx;x<=maxx;++x) {
+ size_t offset = ((size_t)p1.y*w) + x;
+ if (offset >= len) {
+ printf("invalid offset x %zu (y=%d,w=%d,minmax=%d-%d,x=%d,len=%zu,t=%zu)\n", offset, p1.y,w,minx,maxx,x,len, ((size_t)p1.y*w)+x);
+ exit(1);
+ }
+ pic[offset] = '1';
+ }
+ }
+ }
+ puts("pic generate ok");
+ //fsync(f);
+ //if (write(f, pic, len) != (int)len) ("error writing file");
+ size_t chunk = sizeof(char) * 1024 * 1024 * 10;
+ if (chunk>len) chunk=len;
+ printf("chunk: %zu\n", chunk);
+ for (size_t i=0;i<len;i += chunk) {
+ if (len!=chunk && len/chunk == 0) chunk = len%chunk;
+ printf("write chunk %zu of size %zu (real %d)\n", i, chunk, n);
+ n = write(f, pic+i, chunk);
+ }
+ fsync(f);
+ close(f);
+}
+
+int main(void) {
+ int64_t part1 = 0;
+ int64_t part2 = 0;
+ Point *points = calloc(MAX_POINTS, sizeof(Point));
+ int points_l = 0;
+ int *n = points[0].n;
+ int buf[16] = {0};
+ int bufl = 0;
+ for (int c=getchar();c!=EOF;c=getchar()) {
+ if (c>='0'&&c<='9') buf[bufl++] = c-'0';
+ else if (c==','||c=='\n') {
+ *n = btoi(bufl, buf);
+ bufl = 0;
+ n++;
+ if (c=='\n') n = points[++points_l].n;
+ }
+ if (points_l>MAX_POINTS) {
+ printf("Too many input points, max: %d\n", MAX_POINTS);
+ return 1;
+ }
+ }
+ //printf("%d points\n", points_l);
+ int maxx = get_max_x(points_l, points);
+ //printf("maxx: %d\n", maxx);
+ int lines_max = points_l;
+ Line lines[lines_max];
+ int lines_l = 0;
+ for (int i=0;i<points_l-1;++i) {
+ lines[lines_l++] = (Line){ points[i], points[i+1] };
+ }
+ lines[lines_l++] = (Line){ points[0], points[points_l-1] };
+ //gen_pbm(lines_l, lines);
+ (void)gen_pbm;
+ int squares_max = (points_l*points_l-points_l)/2;
+ int64_t squares[squares_max];
+ int squares_l = 0;
+ int64_t squares2[squares_max];
+ int squares2_l = 0;
+ for (int i=0;i<points_l;++i) {
+ for (int j=i;j<points_l;++j) {
+ if (i==j) continue;
+ int64_t sq = square(points[i], points[j]);
+ squares[squares_l++] = sq;
+ //printf("----------------------\n");
+ if (!square_has_points(points_l, points, points[i], points[j]) &&
+ square_valid(lines_l, lines, maxx, points[i], points[j])) {
+ squares2[squares2_l++] = sq;
+ //printf("square %d,%d->%d,%d valid %lu\n", points[i].x,points[i].y, points[j].x,points[j].y,sq);
+ }
+ }
+ }
+ //printf("%d/%d squares\n", squares2_l, squares_max);
+ qsort(squares, squares_l, sizeof(squares[0]), cmp_int64);
+ qsort(squares2, squares2_l, sizeof(squares2[0]), cmp_int64);
+ //for (int i=0;i<squares2_l;++i) printf("%"PRIu64"\n", squares2[i]);
+ part1 = squares[0];
+ part2 = squares2[0];
+ free(points);
+ printf("p1: %"PRIi64"\np2: %"PRIi64"\n", part1, part2);
+ return 0;
+}
+// 1433117952 too low
