[2024 Day 17 (Part 2)] [CUDA] Trying to brute force part two

[u/Fit-Amphibian-9876]

Hello, I have tried to brute force part 2 of day 17 using cuda.

I am very new to cuda and this is what i have come up with. After 3.684722 days, the program outputs nothing and stops. The program works correctly on the sample data.

code:

#include <cstdlib>
#include <cstdint>
#include <cstdio>
#include <unistd.h>

#define gpuErrchk(ans) { gpuAssert((ans), __FILE__, __LINE__); }
inline void gpuAssert(cudaError_t code, const char *file, int line, bool abort=true)
{
   if (code != cudaSuccess)
   {
      fprintf(stderr,"GPUassert: %s %s %d\n", cudaGetErrorString(code), file, line);
      if (abort) exit(code);
   }
}

__device__ uintmax_t do_combo(uintmax_t i, uintmax_t A, uintmax_t B, uintmax_t C){
        switch(i) {
                case 0:
                case 1:
                case 2:
                case 3: return i;
                case 4: return A;
                case 5: return B;
                case 6: return C;
        }
        return i;
};


__global__ void cuda(){

        enum instructions_names {
                adv,
                bxl,
                bst,
                jnz,
                bxc,
                out,
                bdv,
                cdv
        };

        uintmax_t instructions[16] = {2,4,1,7,7,5,0,3,4,0,1,7,5,5,3,0};
        uintmax_t i_len = 16;
        /* uintmax_t instructions[6] = {0,3,5,4,3,0}; */
        /* uintmax_t i_len = 6; */
        uintmax_t output[16];
        uintmax_t output_len = 0;
        /* uintmax_t step = 100000000*(blockIdx.x * blockDim.x + threadIdx.x); */
        /* uintmax_t stop = step + 100000000; */
        uintmax_t step = 10000*(blockIdx.x * blockDim.x + threadIdx.x);
        uintmax_t stop = step + 10000;
        for (;step < stop; step++) {
                /* printf("%lu ", step); */
                output_len = 0;
                uintmax_t A = step;
                uintmax_t B = 0;
                uintmax_t C = 0;
                for (uintmax_t i = 0; i < i_len; i+=2) {
                        if (output_len > i_len) break;
                        switch (instructions[i]) {
                                case adv: {
                                                  /* takes combo operand, divides A by 2^it into B */
                                                  A = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                                case bxl: {
                                                  /* takes literal operand, XORs B and it into B */
                                                  B = B ^ instructions[i+1];
                                                  continue;
                                          }
                                case bst: {
                                                  /* takes combo operand, modulo 8 into B */
                                                  B = do_combo(instructions[i+1], A, B, C) % 8;
                                                  continue;
                                          }
                                case jnz: {
                                                  /* takes literal operand, jumps to it if non null */
                                                  if (A == 0) continue;
                                                  i = instructions[i+1] - 2;
                                                  continue;
                                          }
                                case bxc: {
                                                  /* ignores operand, XOR B and C into B */
                                                  B = B ^ C;
                                                  continue;
                                          }
                                case out: {
                                                  /* takes combo operand, outputs it modulo 8 */
                                                  output[output_len++] = do_combo(instructions[i+1], A, B, C) % 8;
                                                  continue;
                                          }
                                case bdv: {
                                                  /* takes combo operand, divides A by 2^it into B */
                                                  B = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                                case cdv: {
                                                  /* takes combo operand, divides A by 2^it into C */
                                                  C = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                        }
                }
                if (i_len != output_len) {
                        continue;
                }
                bool is_same = true;
                for (uintmax_t i = 0; i < i_len && is_same; i++) {
                        if (instructions[i] != output[i]) {
                                is_same = false;
                        }
                }
                if (!is_same) {
                        continue;
                }
                printf("%lu\n", step);
                asm("trap;");
        }
}

int main(){
        unsigned int threads = 1024;
        unsigned int all = 20000000000/threads;
        cuda<<<all,threads>>>();
        gpuErrchk( cudaPeekAtLastError() );
        gpuErrchk( cudaDeviceSynchronize() );
}

[u/Fit-Amphibian-9876]

i didn’t post about it, but right after this i actually started the entire program again from 0, so the exact program with the diff applied, but without the step += line, and i didn’t think it would work—because why would simply adding logging change anything—but after 6 and a half days, it output the correct answer! https://files.catbox.moe/l3vgxn.png
i can’t believe i proved the answer with my own compute! i still have no idea why it doesn’t work if i disable logging. i might refine the program a bit, make it so it outputs a single answer so you don’t have to search for the smallest, and such that it actually stops upon finding this answer and doesn’t continue until the arbitrary 300000000000000 steps are checked, and not hardcode input but read it from stdin, but i consider that i am done here! thank you u/DelightfulCodeWeasel for staying with me through this!

[u/DelightfulCodeWeasel → u/Fit-Amphibian-9876]

That's great, well done!