From be3a5feabe0d97a219bfa0ecac1869075e0c974d Mon Sep 17 00:00:00 2001 From: June McEnroe Date: Tue, 3 Dec 2019 02:02:07 -0500 Subject: Solve day 3 part 2 Dang, I got screwed up by normalizing the lines in place rather than just for the intersection function. When it came to calculating the length of the final segment to the intersection, the "last" point was sometimes the wrong end. --- 2019/day03.c | 43 +++++++++++++++++++++++++++++++++---------- 1 file changed, 33 insertions(+), 10 deletions(-) (limited to '2019') diff --git a/2019/day03.c b/2019/day03.c index 5d45bc0..6336ff7 100644 --- a/2019/day03.c +++ b/2019/day03.c @@ -10,14 +10,6 @@ struct Line { struct Point a, b; }; -static void normalize(struct Line *l) { - if (l->a.x > l->b.x || l->a.y > l->b.y) { - struct Point p = l->a; - l->a = l->b; - l->b = p; - } -} - static size_t parse(struct Line *lines) { char dir; int dist; @@ -33,13 +25,22 @@ static size_t parse(struct Line *lines) { break; case 'R': point.x += dist; break; default: abort(); } - lines[len].b = point; - normalize(&lines[len++]); + lines[len++].b = point; } return len; } +static void normalize(struct Line *l) { + if (l->a.x > l->b.x || l->a.y > l->b.y) { + struct Point p = l->a; + l->a = l->b; + l->b = p; + } +} + static int intersect(struct Point *p, struct Line v, struct Line h) { + normalize(&v); + normalize(&h); if (v.a.x != v.b.x) { struct Line l = v; v = h; @@ -56,6 +57,10 @@ static int intersect(struct Point *p, struct Line v, struct Line h) { return 1; } +static int length(struct Line l) { + return abs(l.b.x - l.a.x) + abs(l.b.y - l.a.y); +} + int main(void) { struct Line aLines[512]; struct Line bLines[512]; @@ -73,4 +78,22 @@ int main(void) { } } printf("%d\n", min); + + min = INT_MAX; + int aSteps = 0; + for (size_t a = 0; a < aLen; ++a) { + int bSteps = 0; + for (size_t b = 0; b < bLen; ++b) { + struct Point p; + if (intersect(&p, aLines[a], bLines[b]) && !(!p.x && !p.y)) { + int steps = aSteps + bSteps; + steps += length((struct Line) { aLines[a].a, p }); + steps += length((struct Line) { bLines[b].a, p }); + if (steps < min) min = steps; + } + bSteps += length(bLines[b]); + } + aSteps += length(aLines[a]); + } + printf("%d\n", min); } -- cgit 1.4.1 r class='nohover'>Commit message (Expand)Author 2019-01-19Fix ordering issue with va_arg callsJune McEnroe 2019-01-19Take event number for save incrJune McEnroe 2019-01-18Add H_SAVE_INCR function to libeditJune McEnroe 2019-01-18Update gfx-cocoa constants for new macOSJune McEnroe 2019-01-17Add Girlpool Tiny Desk ConcertJune McEnroe 2019-01-17Reunify gfx and binJune McEnroe 2019-01-17Reorganize bin and Makefile once againJune McEnroe 2019-01-17Don't use string functions in ttpreJune McEnroe 2019-01-16Fix some symbols in sans8x16June McEnroe 2019-01-15Add basic HISTFILE load and saveJune McEnroe 2019-01-15Add !! alias in cashJune McEnroe 2019-01-15Add shell and unshell targetsJune McEnroe 2019-01-15Use \$ in cash PS1 and add # to RPS1June McEnroe 2019-01-15Use flock(2) when loading and saving historyJune McEnroe 2019-01-15Add sans8x16.psfJune McEnroe 2019-01-14Add guides to psfedJune McEnroe 2019-01-14Check for NULL copy or undo buffers in psfedJune McEnroe 2019-01-14Add cash.7 READMEJune McEnroe 2019-01-14Document old=new argument of fc -sJune McEnroe 2019-01-14Allow replacing empty string with fc old=newJune McEnroe 2019-01-13Enable warnings in libeditJune McEnroe 2019-01-13Show full path in RPS1June McEnroe 2019-01-13Shorten $HOME to ~ in prompt expansionJune McEnroe 2019-01-13Document PSlitJune McEnroe 2019-01-13Document PS0June McEnroe 2019-01-13Set PS0 in cashJune McEnroe 2019-01-13Add PS0June McEnroe 2019-01-13Change default ENV from cashrc to env.shJune McEnroe 2019-01-13Use colours in cash promptsJune McEnroe 2019-01-12Set PSlit like NetBSD shJune McEnroe 2019-01-12Install gnupg2 from pkgsrc and symlink gpgJune McEnroe 2019-01-12Reference cash builtin man pages in cash.1 SEE ALSOJune McEnroe 2019-01-12Restore cash builtin man page datesJune McEnroe 2019-01-12Use local libeditJune McEnroe 2019-01-12Replace libedit MakefileJune McEnroe 2019-01-11Import /usr/src/lib/libedit from NetBSD 8.0June McEnroe 2019-01-11Add PSlit for prompt escapesJune McEnroe 2019-01-11Don't make depend automaticallyJune McEnroe