What are we calling brute force here? Continuing to go through the pair list and merging groups? Is there any other way?
strlcpy
joined 2 months ago
the trap
Re. what connections to process or not? That seems to be like one of those that's either completely obvious when you implement your solution one way, and a nasty pitfall when you do it another. In this case, pre-computing the list of pairs to process vs. finding the next one when you need it.
C
Got stuck for a bit on part 1 on a silly mistake in the group (circuit) merging code, where the nodes from one group are reassigned to the other:
for (i=0; i < nnodes; i++)
if (nodes[i].group == pair->b->group)
nodes[i].group = pair->a->group;
At some point in the loop pair->b.group itself is updated, from then on the check is against the new group value. Oops.
In the end, my solution's runtime on my (10 year old!) PC is about 160 ms for both parts, which is more than I would like, so maybe I'll look into better set representations.
Code
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <assert.h>
#define LEN(a) (sizeof(a)/sizeof(*(a)))
#define NPAIRS(x) ((x)*((x)-1)/2)
#define MAXN 1024
struct node { int x,y,z, group; };
struct pair { struct node *a, *b; int64_t dist_sq; };
struct group { int count; };
static struct node nodes[MAXN];
static struct pair pairs[NPAIRS(MAXN)];
static struct group groups[MAXN];
static int nnodes;
static int ngroups;
static int64_t
node_dist_sq(const struct node *a, const struct node *b)
{
return
(int64_t)(a->x - b->x) * (a->x - b->x) +
(int64_t)(a->y - b->y) * (a->y - b->y) +
(int64_t)(a->z - b->z) * (a->z - b->z);
}
static int
cmp_pairs(const void *va, const void *vb)
{
const struct pair *a = va;
const struct pair *b = vb;
return
a->dist_sq < b->dist_sq ? -1 :
a->dist_sq > b->dist_sq ? 1 : 0;
}
static int
cmp_groups_asc(const void *va, const void *vb)
{
const struct group *a = va;
const struct group *b = vb;
return b->count - a->count;
}
static void
merge_groups(int group_a, int group_b)
{
int i;
if (group_a == group_b)
return;
groups[group_a].count += groups[group_b].count;
groups[group_b].count = 0;
for (i=0; i<nnodes; i++)
if (nodes[i].group == group_b)
nodes[i].group = group_a;
ngroups--;
}
int
main()
{
int p1=0,p2=0, p1_limit, i,j, n,p;
for (; ; nnodes++) {
assert(nnodes < MAXN);
n = scanf(" %d,%d,%d",
&nodes[nnodes].x,
&nodes[nnodes].y,
&nodes[nnodes].z);
if (n < 3)
break;
nodes[nnodes].group = nnodes;
groups[nnodes].count = 1;
}
ngroups = nnodes;
for (p=0, i=0; i<nnodes-1; i++)
for (j=i+1; j<nnodes; j++, p++) {
pairs[p].a = &nodes[i];
pairs[p].b = &nodes[j];
pairs[p].dist_sq = node_dist_sq(&nodes[i], &nodes[j]);
}
qsort(pairs, NPAIRS(nnodes), sizeof(*pairs), cmp_pairs);
p1_limit = nnodes <= 100 ? 10 : 1000;
for (i=0; ngroups > 1; i++) {
merge_groups(pairs[i].a->group, pairs[i].b->group);
if (ngroups == 1)
p2 = pairs[i].a->x * pairs[i].b->x;
if (i == p1_limit) {
qsort(groups, LEN(groups), sizeof(*groups),
cmp_groups_asc);
p1 = groups[0].count *
groups[1].count *
groups[2].count;
}
}
printf("08: %d %d\n", p1, p2);
}
If I understand correctly, your visualization shows up to to 256 unique paths then?
In this one, every time the beam passes a splitter, the other side is put on a queue, so eventually all possible paths are traced, breadth first. Initially I worked through the options recursively, but that depth-first filling out was boring to look at.
Well it uses the input of course but I found that if you make it truly random, the lines mostly go down in a straight line, all bunching up in the middle, which isn't very pleasing. So now the beams have a "current direction" which has a 25% of flipping at every splitter
In 16-bit real mode assembly, as a hybrid DOS .COM program and BIOS-bootable disk image. With bonus palette animations! I had the hybrid thing going on before (see the repo), but this is the first time getting something animated.
Repo | day07.com (12 KB) | full video
Ahh I knew there would be some simple combined representation like this but couldn't be bothered. Nice!
C
Accidentally solved part 2 first but had the foresight to save the code. Otherwise my solution looks similar to what other people are doing, just with more code ๐
Code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <assert.h>
#define GW 148
#define GH 74
static char g[GH][GW];
static uint64_t dp[2][GW];
static int w,h;
/* recursively traces beam for part 1, marking visited splitters with 'X' */
static uint64_t
solve_p1(int x, int y)
{
if (x<0 || x>=w || y<0 || y>=h || g[y][x] == 'X')
return 0;
else if (g[y][x] != '^')
return solve_p1(x, y+1);
else {
g[y][x] = 'X';
return 1 + solve_p1(x-1, y) + solve_p1(x+1, y);
}
}
/* DP for part 2 */
static uint64_t
solve_p2(void)
{
int x,y, odd;
for (y=h-1; y>=0; y--)
for (x=1; x<w-1; x++) {
/* only two rows relevant at a time, so don't store any more */
odd = y&1;
if (g[y][x] == 'S') {
printf("\n");
return dp[!odd][x] + 1;
}
dp[odd][x] = g[y][x] == '^' || g[y][x] == 'X'
? dp[!odd][x-1] + dp[!odd][x+1] + 1
: dp[!odd][x];
}
return 0;
}
int
main()
{
int x,y, sx,sy;
for (h=0; ; ) {
/* one bottom row of padding */
assert(h < GH-1);
/* input already side padded, plus we have \n\0 */
if (!fgets(g[h], GW, stdin))
break;
/* skip empty rows */
for (x=0; g[h][x]; x++)
if (g[h][x] == 'S' || g[h][x] == '^')
{ h++; break; }
}
w = strlen(g[0])-1; /* strip \n */
for (y=0; y<h; y++)
for (x=0; x<w; x++)
if (g[y][x] == 'S')
{ sx=x; sy=y; break; }
printf("07: %"PRIu64" %"PRIu64"\n", solve_p1(sx,sy), solve_p2());
}
C
Well so much for reading a grid of ints in part 1! For part 2, initially I reworked the parsing to read into a big buffer, but then thought it would be fun to try and use memory-mapped I/O as not to use any more memory than strictly necessary for the final version:
Code
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <assert.h>
#include <sys/mman.h>
#include <unistd.h>
#include <err.h>
#define GH 5
int
main()
{
char *data, *g[GH], *p;
uint64_t p1=0,p2=0, acc;
int len, h=0, i, x,y, val;
char op;
if ((len = (int)lseek(0, 0, SEEK_END)) == -1)
err(1, "<stdin>");
if (!(data = mmap(NULL, len, PROT_READ, MAP_SHARED, 0, 0)))
err(1, "<stdin>");
for (i=0; i<len; i++)
if (!i || data[i-1]=='\n') {
assert(h < GH);
g[h++] = data+i;
}
for (x=0; g[h-1]+x < data+len; x++) {
if ((op = g[h-1][x]) != '+' && op != '*')
continue;
for (acc = op=='*', y=0; y<h-1; y++) {
val = atoi(&g[y][x]);
acc = op=='+' ? acc+val : acc*val;
}
p1 += acc;
for (acc = op=='*', i=0; ; i++) {
for (val=0, y=0; y<h-1; y++) {
p = &g[y][x+i];
if (p < g[y+1] && isdigit(*p))
val = val*10 + *p-'0';
}
if (!val)
break;
acc = op=='+' ? acc+val : acc*val;
}
p2 += acc;
}
printf("06: %"PRIu64" %"PRIu64"\n", p1, p2);
}
C
Sweet one. Glad the merge could be done with one n^2^/2 scan and no sorting or moving, which will make the assembly port a bit easier. Speaking of which, I'm still at day 3 there, fighting not the puzzles but the 64K .COM file limit!
Code
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#define MR 256
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
struct range { uint64_t lo, hi; };
static struct range rs[MR];
static int nrs;
int
main()
{
uint64_t p1=0,p2=0, val;
int i,j;
char buf[64];
for (; fgets(buf, sizeof(buf), stdin); nrs++) {
assert(nrs < MR);
if (sscanf(buf, "%lu-%lu", &rs[nrs].lo, &rs[nrs].hi) != 2)
break;
}
for (i=0; i<nrs-1; i++)
for (j=i+1; j<nrs; j++)
if (rs[i].lo <= rs[j].hi && rs[i].hi >= rs[j].lo) {
rs[j].lo = MIN(rs[i].lo, rs[j].lo);
rs[j].hi = MAX(rs[i].hi, rs[j].hi);
rs[i].lo = rs[i].hi = 0;
}
while (scanf("%lu", &val) == 1)
for (i=0; i<nrs; i++)
if (val >= rs[i].lo && val <= rs[i].hi)
{ p1++; break; }
for (i=0; i<nrs; i++)
if (rs[i].lo)
p2 += rs[i].hi - rs[i].lo + 1;
printf("05: %lu %lu\n", p1, p2);
}
C
For loops!
Code
#include <stdio.h>
#define GZ 144
static char g[GZ][GZ];
int
main()
{
int p1=0,p2=0, nc=0, x,y;
for (y=1; fgets(g[y]+1, GZ-2, stdin); y++)
;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
p1 += g[y][x] == '@' &&
(g[y-1][x-1] == '@') +
(g[y-1][x ] == '@') +
(g[y-1][x+1] == '@') +
(g[y ][x-1] == '@') +
(g[y ][x+1] == '@') +
(g[y+1][x-1] == '@') +
(g[y+1][x ] == '@') +
(g[y+1][x+1] == '@') < 4;
do {
nc = 0;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
if (g[y][x] == '@' &&
(g[y-1][x-1] == '@') +
(g[y-1][x ] == '@') +
(g[y-1][x+1] == '@') +
(g[y ][x-1] == '@') +
(g[y ][x+1] == '@') +
(g[y+1][x-1] == '@') +
(g[y+1][x ] == '@') +
(g[y+1][x+1] == '@') < 4) {
nc++;
p2++;
g[y][x] = '.';
}
} while (nc);
printf("04: %d %d\n", p1, p2);
return 0;
}
For my x86-16 version, the 20K input is pushing it over the 64K .COM limit, so I'll need to implement some better compression first.
view more: next โบ
Work: Windows + Rider/WebStorm/etc (I used the IdeaVim plugin before but found there were too many rough edges)
Home: Debian or OpenBSD + vi or Pluma. I deliberately keep it simple. A terminal, an editor Ctrl+Z, make, fg, that kind of thing. I'm tired of fighting IDEs to get out of my way. Let me type!