Day 9: Movie Theater

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • sjmulder@lemmy.sdf.org
    link
    fedilink
    English
    arrow-up
    2
    ·
    edit-2
    2 days ago

    C

    Well this one got me stumped for a bit but after a few false starts, lots of debugging and some cleanup I’d say I have a pretty good solution now! The points being tiles rather than zero-width corners was the tricky bit here.

    Basic working: it walks through the points, keeping track of normal vectors (the “outside” direction). With those, it generates the zero-width outline around the points, and from there on it’s pretty much old fashioned line intersection checks.

    The initial nasty solve took 1.2 seconds on my Raspberry Pi 400, but some optimization (like sorting the edges list) brought that down to 0.08s on the Pi, and 0.02s on my 10-year old PC, and I’m quite happy with the code now.

    Code
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <inttypes.h>
    #include <assert.h>
    
    #define MIN(a,b)	((a)<(b)?(a):(b))
    #define MAX(a,b)	((a)>(b)?(a):(b))
    #define LEN(a)		(sizeof(a)/sizeof(*(a)))
    
    #define MAXP	512
    
    /*
     * There are two main problems with part 2:
     *  1. Deciding what is inside and what is outside of the polyline
     *  2. The points being _tiles_, not zero-width coordinates
     *
     * This solution walks the outline and calculates "normals" for each
     * point, which are angles pointing _out_ of the shape. Those are used
     * to derrive the outside boundary of the shape, the lines that go
     * around, not through, the corner tiles. Witth that we can do
     * more-or-less normal intersection checks.
     *
     * Angles are stored as 1/8ths of a circle.
     */
    
    struct point { int x,y; };
    struct edge { int off, lo,hi; };
    
    static struct point pts[MAXP];
    static struct edge hedges[MAXP/2];
    static struct edge vedges[MAXP/2];
    static int norms[MAXP];
    static int np, nhe, nve;
    
    static int wrapa(int a) { return (a+8)%8; }
    
    static int
    cmp_edges(const void *a, const void *b)
    {
    	return ((const struct edge *)a)->off -
    	       ((const struct edge *)b)->off;
    }
    
    static int
    line_dir(struct point a, struct point b)
    {
    	return 4*(a.x>b.x || a.y<b.y) + 2*(a.x!=b.x);
    }
    
    static void
    calculate_normals(void)
    {
    	int i, dir1,dir2, angle;
    	int normal; /* relative to the current line  */
    
    	dir1 = line_dir(pts[np-1], pts[0]);
    	normal = wrapa(dir1 - 2); /* start left, assuming CCW order */
    
    	for (i=0; i<np; i++) {
    		dir2 = line_dir(pts[i], pts[i==np-1 ? 0 : i+1]);
    		angle = dir2 == dir1-2 || dir2 == dir1+6 ? -2 : 2;
    
    		/* the point's normal is diagonal, halfway turned */
    		norms[i] = wrapa(normal + angle/2);
    
    		dir1 = dir2;
    		normal = wrapa(normal + angle);
    	}
    }
    
    static void
    generate_edges(void)
    {
    	struct point a,b;
    	int i,j;
    
    	for (i=0; i<np; i++) {
    		a = pts[i];
    		b = pts[(j = i==np-1 ? 0 : i+1)];
    
    		/* shift the line to be _around_ point */
    		a.x += norms[i]<4; a.y += norms[i]>2 && norms[i]<6;
    		b.x += norms[j]<4; b.y += norms[j]>2 && norms[j]<6;
    
    		if (a.x == b.x) {
    			assert(nve < (int)LEN(vedges));
    			vedges[nve].off = a.x;
    			vedges[nve].lo = MIN(a.y, b.y);
    			vedges[nve].hi = MAX(a.y, b.y);
    			nve++;
    		} else if (a.y == b.y) {
    			assert(nhe < (int)LEN(hedges));
    			hedges[nhe].off = a.y;
    			hedges[nhe].lo = MIN(a.x, b.x);
    			hedges[nhe].hi = MAX(a.x, b.x);
    			nhe++;
    		} else
    			assert(!"diagonal line");
    	}
    
    	qsort(hedges, nhe, sizeof(*hedges), cmp_edges);
    	qsort(vedges, nve, sizeof(*vedges), cmp_edges);
    }
    
    static bool
    rect_inside(struct point a, struct point b)
    {
    	struct edge *e;
    	int x0,y0,x1,y1;
    
    	/*
    	 * Line intersection of the four rectangle edges against all
    	 * the polyline edges, with a caveat: the outline is 1 unit
    	 * thick, not zero-width! This is why some of the comparisons
    	 * are or-equals.
    	 */
    
    	x0 = MIN(a.x, b.x); y0 = MIN(a.y, b.y);
    	x1 = MAX(a.x, b.x); y1 = MAX(a.y, b.y);
    
    	for (e = vedges; e < vedges+nve; e++) {
    		if (e->off <= x0) continue;
    		if (e->off > x1) break;
    		if (y0 >= e->lo && y0 < e->hi) return false;
    		if (y1 >= e->lo && y1 < e->hi) return false;
    	}
    
    	for (e = hedges; e < hedges+nhe; e++) {
    		if (e->off <= y0) continue;
    		if (e->off > y1) break;
    		if (x0 >= e->lo && x0 < e->hi) return false;
    		if (x1 >= e->lo && x1 < e->hi) return false;
    	}
    
    	return true;
    }
    
    int
    main()
    {
    	int64_t p1=0,p2=0, area, i,j;
    
    	for (; scanf(" %d,%d", &pts[np].x, &pts[np].y)==2; np++)
    		assert(np+1 < MAXP);
    	
    	assert(np >= 4);
    
    	calculate_normals();
    	generate_edges();
    
    	for (i=0; i<np-1; i++)
    	for (j=i+1; j<np; j++) {
    		area = (int64_t)(abs(pts[i].x - pts[j].x) + 1) *
    		       (int64_t)(abs(pts[i].y - pts[j].y) + 1);
    		if (area > p1)
    			p1 = area;
    		if (area > p2 && rect_inside(pts[i], pts[j]))
    			p2 = area;
    	}
    
    	printf("09: %"PRIi64" %"PRIi64"\n", p1, p2);
    }