Advent of Code

Check-in [367ff5ba4e]
Login

Check-in [367ff5ba4e]

Overview
Comment:202422 2nd star -- brute force 30 mins runtime
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 367ff5ba4e74eb7808bfc0939dc8ddf7cd419659e48211f139e62bb5075316f6
User & Date: nnz on 2025-01-12 15:44:03
Other Links: manifest | tags
Context
2025-01-12
17:28
brought 202422 down to under 10 minutes Leaf check-in: f0e101dfbf user: nnz tags: trunk
15:44
202422 2nd star -- brute force 30 mins runtime check-in: 367ff5ba4e user: nnz tags: trunk
2025-01-09
19:37
revamped the comma separated output check-in: 2f90165e39 user: nnz tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Modified aoc2024.c from [5c45b25c23] to [0631d1d281]. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20















21
22
23
24


25
26
27
28



29
30

31
32
33
34

35
36
37










































38
39
40
41
42
43
44

1
2
3
4
5
6
7
8
9
10

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


43
44
45
46

47


48

49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101











-









+
+
+
+
+
+
+
+
+
+
+
+
+
+
+




+
+


-
-
+
+
+

-
+
-
-

-
+



+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+








#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "aocdailies.h"
#include "aocutils.h"

/* === aoc202422 =======================================================
TODO: Part Two
===================================================================== */
static long long unsigned mix(long long unsigned a, long long unsigned b) {
    long long unsigned tmp = a ^ b;
    return tmp;
}

static long long unsigned prune(long long unsigned a) {
    return a % 16777216;
}

static void nextsecret(long long unsigned sec[2]) {
    sec[0] = sec[1];
    sec[1] = prune(mix(sec[0] * 64, sec[0]));
    sec[1] = prune(mix(sec[1] / 32, sec[1]));
    sec[1] = prune(mix(sec[1] * 2048, sec[1]));
}

static int deltamatch(int delta[4], int c[4]) {
    if (delta[0] != c[0]) return 0;
    if (delta[1] != c[1]) return 0;
    if (delta[2] != c[2]) return 0;
    if (delta[3] != c[3]) return 0;
    return 1;
}

void aoc202422(char *data, size_t len) {
    (void)len; // unused argument
    long long unsigned sum2000 = 0;
    long long unsigned secrets[2000] = {0};
    size_t nsecrets = 0;
    char *key = strtok(data, "\n");
    while (key) {
        long long unsigned secret;
        if (sscanf(key, "%llu", &secret) != 1) break;
        long long unsigned secret[2];
        if (sscanf(key, "%llu", secret + 1) != 1) break;
        secrets[nsecrets++] = secret[1];
        for (int k = 0; k < 2000; k++) {
            secret = prune(mix(secret * 64, secret));
            nextsecret(secret);
            secret = prune(mix(secret / 32, secret));
            secret = prune(mix(secret * 2048, secret));
        }
        sum2000 += secret;
        sum2000 += secret[1];
        key = strtok(NULL, "\n");
    }
    printf("The sum of all 2000th secrets is {%llu}.\n", sum2000);

    int c[4];
    int maxbananas = 0, totalbananas = 0;
    for (c[0] = -9; c[0] < 10; c[0]++) {
        for (c[1] = -9; c[1] < 10; c[1]++) {
            for (c[2] = -9; c[2] < 10; c[2]++) {
                for (c[3] = -9; c[3] < 10; c[3]++) {
                    totalbananas = 0;
                    for (size_t s = 0; s < nsecrets; s++) {
                        int bananas = 0;
                        unsigned long long sec[2] = {0, secrets[s]};
                        int delta[4];
                        //round0
                        nextsecret(sec);
                        delta[0] = (sec[1] % 10) - (sec[0] % 10);
                        //round1
                        nextsecret(sec);
                        delta[1] = (sec[1] % 10) - (sec[0] % 10);
                        //round2
                        nextsecret(sec);
                        delta[2] = (sec[1] % 10) - (sec[0] % 10);
                        for (int round = 3; round < 2000; round++) {
                            nextsecret(sec);
                            delta[3] = (sec[1] % 10) - (sec[0] % 10);
                            if (deltamatch(delta, c)) {
                                bananas = sec[1] % 10;
                                break;
                            }
                            delta[0] = delta[1];
                            delta[1] = delta[2];
                            delta[2] = delta[3];
                        }
                        totalbananas += bananas;
                    }
                    if (totalbananas > maxbananas) {
                        maxbananas = totalbananas;
                    }
                }
            }
        }
    }
    printf("Maximum bananas is (%d).\n", maxbananas);
}

/* === aoc202417 =======================================================
TODO: proper (recursive) solution for Part Two
===================================================================== */

static unsigned combo(unsigned operand, unsigned long long r[3]) {
︙
68
69
70
71
72
73
74






























75
76
77
78
79
80
81

125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168








+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+








                *outlen += 1;
                break;
        case 6: r[1] = r[0] / (1 << combo(operand, r)); break;
        case 7: r[2] = r[0] / (1 << combo(operand, r)); break;
    }
    return nextip;
}

static unsigned long long findquine(unsigned *p, unsigned np,
      long long unsigned reg[4], unsigned sets3bits) {
    reg[0] = reg[3];
    reg[1] = reg[2] = 0;

    unsigned output[100];
    size_t outlen = 0;
    unsigned ip = 0;
    while (ip + 1 < np) {
        ip = instruction(ip, p[ip], p[ip+1], reg, output, &outlen);
    }

    if (outlen > np) return 0;
    if (outlen == np) {
        for (unsigned k = 0; k < np; k++) {
            if (output[k] != p[k]) return 0;
        }
        return 1;
    }
    unsigned long long saved3 = reg[3];
    for (unsigned k = 0; k < 8; k++) {
        reg[3] = (saved3 << 3) + k;
        if (findquine(p, np, reg, sets3bits + 1)) {
            return 1;
        }
        reg[3] = saved3;
    }
    return 0;
}

void aoc202417(char *data, size_t len) {
    (void)len; //unused argument
    unsigned long long reg[4]; // A, B, and C ... and copy of A for Part Two
    char *dta = strstr(data, " A: "), *err;
    reg[0] = strtoull(dta + 4, &err, 10);
    dta = strstr(err, " B: ");
︙
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124



125




126
127
128
129
130
131
132

191
192
193
194
195
196
197

198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213

214
215
216
217
218
219
220
221
222
223
224








-













+
+
+
-
+
+
+
+









    printf("Program is          (%u", p[0]);
    for (unsigned k = 1; k < np; k++) {
        printf(",%u", p[k]);
    }
    printf(")\n");

    reg[3] = 202322936867370;
#if 0
    // I'm not happy with my "solution".
    // It wasn't the program who found it.
    // I found it by studying closer and closer attempts

    // first I noticed that the program work 3 bits at a time,
    // so, to generate a sequence with 16 numbers it needs 48 bits

    // I then simply calculated the output with each 3-bit value one-by-one
    // until I had the whole thing

    // someday, maybe, I'll try to write a proper recursive solution
#else
    reg[3] = 202322936867370;
    reg[3] = 0;
    if (findquine(p, np, reg, 0)) {
    printf("Start with A = %llu to get the quine.\n", reg[3]);
        printf("Start with A = %llu to get the quine.\n", reg[3]);
    } else {
        printf("Quine not found :(\n");
    }
#endif
}

/* === aoc202409 =======================================================
   WOW! input consists of a 20,000 long string of numbers!
   Make an array of blocks, each with either -1 or the fileid
   For Part Two: make an array of blocks with the encoded value of
︙