SHARE
TWEET

Untitled

a guest Dec 2nd, 2019 119 in 3 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _GNU_SOURCE
  2.  
  3. #include <errno.h>
  4. #include <math.h>
  5. #include <stdbool.h>
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9.  
  10. #define NELEMS(x) (sizeof(x) / sizeof((x)[0]))
  11.  
  12. typedef enum { Add = 1, Multiply = 2, Halt = 99 } OpCode;
  13.  
  14. typedef struct {
  15.   OpCode op;
  16.   unsigned int mem_idx1;
  17.   unsigned int mem_idx2;
  18.   unsigned int mem_dest;
  19. } Instruction;
  20.  
  21. static bool perform_instruction(unsigned int mem_array[static 145],
  22.                                 Instruction curr_instruction) {
  23.   const unsigned int val1 = mem_array[curr_instruction.mem_idx1];
  24.   const unsigned int val2 = mem_array[curr_instruction.mem_idx2];
  25.  
  26.   switch (curr_instruction.op) {
  27.     case Add:
  28.       mem_array[curr_instruction.mem_dest] = val1 + val2;
  29.       return true;
  30.  
  31.     case Multiply:
  32.       mem_array[curr_instruction.mem_dest] = val1 * val2;
  33.       return true;
  34.  
  35.     case Halt:
  36.       return false;
  37.  
  38.     default:
  39.       fprintf(stderr, "Unknown opcode encountered");
  40.       exit(EXIT_FAILURE);
  41.       break;
  42.   }
  43. }
  44.  
  45. // populate next instruction & advance instruction pointer
  46. static bool get_next_op(unsigned int mem_array[static 145], Instruction* op_out,
  47.                         int* curr_idx) {
  48.   const OpCode curr_op = mem_array[*curr_idx];
  49.   op_out->op = curr_op;
  50.  
  51.   if (curr_op == Halt) {
  52.     *curr_idx += 1;
  53.     return true;
  54.   } else {
  55.     op_out->mem_idx1 = mem_array[(*curr_idx) + 1];
  56.     op_out->mem_idx2 = mem_array[(*curr_idx) + 2];
  57.     op_out->mem_dest = mem_array[(*curr_idx) + 3];
  58.  
  59.     *curr_idx += 4;
  60.     return true;
  61.   }
  62. }
  63.  
  64. // parse initial memory state from stdin
  65. static void init_memory(char* buf, unsigned int mem_array[static 145]) {
  66.   int mem_idx = 0;
  67.  
  68.   char* curr_token = strtok(buf, ",");
  69.  
  70.   while (curr_token != NULL) {
  71.     errno = 0;
  72.     const unsigned int parsed_uint =
  73.         (unsigned int)strtoul(curr_token, NULL, 10);
  74.  
  75.     if (errno) {
  76.       perror("Failed to parse instruction stream!");
  77.       exit(EXIT_FAILURE);
  78.     } else {
  79.       mem_array[mem_idx++] = parsed_uint;
  80.     }
  81.  
  82.     curr_token = strtok(NULL, ",");
  83.   }
  84. }
  85.  
  86. static void run_program(unsigned int mem[static 145]) {
  87.   int pc = 0;
  88.   Instruction curr_op = {0};
  89.  
  90.   while (get_next_op(mem, &curr_op, &pc)) {
  91.     const bool instruction_result = perform_instruction(mem, curr_op);
  92.     if (!instruction_result) break;
  93.   }
  94. }
  95.  
  96. static void saddleback_search(unsigned int work_mem[static 145],
  97.                               unsigned int img_mem[static 145]) {
  98.   const int expected_result = 19690720;
  99.   unsigned int counter = 0;
  100.   int run_result = 0;
  101.   int middle1 = 0, middle2 = 0;
  102.  
  103.   int val1_l = 0, val1_r = 99;
  104.   while (val1_l <= val1_r) {
  105.     int val2_l = 0, val2_r = 99;
  106.     while (val2_l <= val2_r) {
  107.       memcpy(work_mem, img_mem, 145 * sizeof(unsigned int));
  108.       counter++;
  109.  
  110.       middle1 = (int)floor((val1_l + val1_r) / 2.0);
  111.       middle2 = (int)floor((val2_l + val2_r) / 2.0);
  112.  
  113.       work_mem[1] = (unsigned int)middle1;
  114.       work_mem[2] = (unsigned int)middle2;
  115.  
  116.       run_program(work_mem);
  117.  
  118.       run_result = (int)work_mem[0];
  119.  
  120.       if (run_result == expected_result) {
  121.         printf("1: %u\n2: %u\nNum of tries: %u", work_mem[1], work_mem[2],
  122.                counter);
  123.         exit(EXIT_SUCCESS);
  124.       } else if (run_result < expected_result) {
  125.         val2_l = (int)middle2 + 1;
  126.       } else {
  127.         val2_r = (int)middle2 - 1;
  128.       }
  129.     }
  130.     if (run_result < expected_result) {
  131.       val1_l = (int)middle1 + 1;
  132.     } else {
  133.       val1_r = (int)middle1 - 1;
  134.     }
  135.   }
  136. }
  137.  
  138. int main() {
  139.   unsigned int mem_img[145] = {0};
  140.  
  141.   char* curr_line = NULL;
  142.   size_t len = 0;
  143.  
  144.   if (getline(&curr_line, &len, stdin) == -1) {
  145.     perror("Problem while reading line from stdin");
  146.   }
  147.  
  148.   init_memory(curr_line, mem_img);
  149.  
  150.   unsigned int mem_work[145] = {0};
  151.   memcpy(mem_work, mem_img, 145 * sizeof(unsigned int));
  152.  
  153.   run_program(mem_work);
  154.  
  155.   printf("%u\n", mem_work[0]);
  156.   printf("Part 2:\n");
  157.  
  158.   saddleback_search(mem_work, mem_img);
  159. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top