From e3174e30fc2cd524ea31bf2a81c43d2a2500c1d5 Mon Sep 17 00:00:00 2001 From: June McEnroe Date: Fri, 21 Dec 2018 04:29:50 -0500 Subject: Solve day 18 part 2 --- 2018/day18.c | 56 +++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 49 insertions(+), 7 deletions(-) (limited to '2018') diff --git a/2018/day18.c b/2018/day18.c index 686ae70..6bc55f7 100644 --- a/2018/day18.c +++ b/2018/day18.c @@ -1,5 +1,7 @@ +#include #include #include +#include typedef unsigned uint; @@ -52,6 +54,42 @@ static struct Map step(struct Map prev) { return next; } +static uint value(struct Map map) { + uint wood = 0, lumber = 0; + for (uint y = 0; y < 50; ++y) { + for (uint x = 0; x < 50; ++x) { + if (map.acres[y][x] == '|') wood++; + if (map.acres[y][x] == '#') lumber++; + } + } + return wood * lumber; +} + +enum { RingLen = 64 }; +static_assert(!(RingLen & (RingLen - 1)), "power of two"); + +static struct { + struct Map buf[RingLen]; + uint end; +} ring; + +static struct Map *ringMap(uint i) { + return &ring.buf[(ring.end + i) & (RingLen - 1)]; +} + +static void ringPush(struct Map map) { + *ringMap(0) = map; + ring.end++; +} + +static uint ringFind(struct Map map) { + uint i; + for (i = 0; i < RingLen; ++i) { + if (!memcmp(ringMap(i), &map, sizeof(map))) break; + } + return i; +} + int main(void) { struct Map map; for (uint y = 0; y < 50; ++y) { @@ -61,12 +99,16 @@ int main(void) { for (uint i = 0; i < 10; ++i) { map = step(map); } - uint wood = 0, lumber = 0; - for (uint y = 0; y < 50; ++y) { - for (uint x = 0; x < 50; ++x) { - if (map.acres[y][x] == '|') wood++; - if (map.acres[y][x] == '#') lumber++; - } + printf("%u\n", value(map)); + + uint i; + for (i = 11; i < 1000000000; ++i) { + map = step(map); + if (ringFind(map) < RingLen) break; + ringPush(map); } - printf("%u\n", wood * lumber); + uint skip = ringFind(map); + uint period = RingLen - skip; + uint final = skip + (1000000000 - i) % period; + printf("%u\n", value(*ringMap(final))); } -- cgit 1.4.1 ='submit' value='search'/>
path: root/html.c (unfollow)
Commit message (Collapse)Author
2006-12-11Move global variables + callback functions into shared.cLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Move functions for generic object output into ui-view.cLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Move log-functions into ui-log.cLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Move repo summary functions into ui-summary.cLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Move functions for repolist output into ui-repolist.cLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Move common output-functions into ui-shared.cLars Hjemli
While at it, replace the cgit_[lib_]error constants with a proper function Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Rename config.c to parsing.c + move cgit_parse_query from cgit.c to parsing.cLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Avoid infinite loops in caching layerLars Hjemli
Add a global variable, cgit_max_lock_attemps, to avoid the possibility of infinite loops when failing to acquire a lockfile. This could happen on broken setups or under crazy server load. Incidentally, this also fixes a lurking bug in cache_lock() where an uninitialized returnvalue was used. Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Let 'make install' clear all cachefilesLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-11Fix cache algorithm loopholeLars Hjemli
This closes the door for unneccessary calls to cgit_fill_cache(). Noticed by Linus. Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-10Add version identifier in generated filesLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-10Add license file and copyright noticesLars Hjemli
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
2006-12-10Add caching infrastructureLars Hjemli