Skip to content

Instantly share code, notes, and snippets.

@erikaderstedt

erikaderstedt/p15.c

Created December 16, 2019 10:10
Show Gist options
  • Save erikaderstedt/1bf97005bfb57cb0027455564066351d to your computer and use it in GitHub Desktop.
Save erikaderstedt/1bf97005bfb57cb0027455564066351d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
p15.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "intcode.h"
#define MAX_NUM_OUTPUTS 10
int find_oxygen_generator(int64_t x, int64_t y, int64_t *visited, size_t *num_visited, struct program *p, int nsteps,
struct program **drone_at_oxygen_generator, int64_t *generator_x, int64_t *generator_y) {
visited[*num_visited] = x*1000+y;
*num_visited = (*num_visited) + 1;
int64_t input;
bool h = false;
int best = 1000000;
for (size_t d = 1; d <= 4; d++) {
int64_t x2 = x, y2 = y, r = 0;
switch (d) {
case 1: y2--; r = 2; break;
case 2: y2++; r = 1; break;
case 3: x2--; r = 4; break;
case 4: x2++; r = 3; break;
}
int64_t j = x2*1000+y2;
size_t xx;
for (xx = 0; xx < (*num_visited) && (visited[xx] != j); xx++);
if (xx == *num_visited) {
input = d;
p->input = &input;
p->remaining_inputs = 1;
h = run_program_instance_until_halted(p);
int64_t o = p->output[0];
if (o == 0) {
// Add to visited,
visited[*num_visited] = j;
*num_visited = (*num_visited) + 1;
} else if (o == 1) {
struct program *p2 = copy_program(p);
int m = find_oxygen_generator(x2, y2, visited, num_visited, p2, nsteps+1, drone_at_oxygen_generator, generator_x, generator_y);
if (m < best) {
best = m;
}
free_program_instance(p2);
// Go back
p->input = &r;
p->remaining_inputs = 1;
h = run_program_instance_until_halted(p);
} else if (o == 2) {
best = nsteps + 1;
if (*drone_at_oxygen_generator == NULL) {
*drone_at_oxygen_generator = copy_program(p);
*generator_y = y2;
*generator_x = x2;
}
}
}
}
if (h) printf("Halted\n");
return best;
}
int fill_with_oxygen(int64_t x, int64_t y, int64_t *visited, size_t *num_visited, struct program *p, int nsteps) {
visited[*num_visited] = x*1000+y;
*num_visited = (*num_visited) + 1;
int64_t input;
bool h = false;
int best = nsteps;
for (size_t d = 1; d <= 4; d++) {
int64_t x2 = x, y2 = y, r = 0;
switch (d) {
case 1: y2--; r = 2; break;
case 2: y2++; r = 1; break;
case 3: x2--; r = 4; break;
case 4: x2++; r = 3; break;
}
int64_t j = x2*1000+y2;
size_t xx;
for (xx = 0; xx < (*num_visited) && (visited[xx] != j); xx++);
if (xx == *num_visited) {
input = d;
p->input = &input;
p->remaining_inputs = 1;
h = run_program_instance_until_halted(p);
int64_t o = p->output[0];
if (o == 0) {
// Add to visited,
visited[*num_visited] = j;
*num_visited = (*num_visited) + 1;
} else if (o == 1) {
struct program *p2 = copy_program(p);
int m = fill_with_oxygen(x2, y2, visited, num_visited, p2, nsteps+1);
if (m > best) {
best = m;
}
free_program_instance(p2);
// Go back
p->input = &r;
p->remaining_inputs = 1;
h = run_program_instance_until_halted(p);
}
}
}
if (h) printf("Halted\n");
return best;
}
int main(int argc, char **argv) {
int64_t output[MAX_NUM_OUTPUTS];
int64_t visited[100*100];
size_t num_visited = 0;
size_t length;
int64_t *source = load_source_code_from_file(argv[1], &length, 1000);
struct program *p = init_program_instance(source, length, output);
struct program *drone_at_oxygen_generator = NULL;
int64_t generator_x;
int64_t generator_y;
int64_t x = 0, y = 0;
int m = find_oxygen_generator(x, y, visited, &num_visited, p, 0, &drone_at_oxygen_generator, &generator_x, &generator_y);
printf("Pt 1: %d\n", m);
free_program_instance(p);
memset(visited, 0, 100*100);
num_visited = 0;
m = fill_with_oxygen(generator_x, generator_y, visited, &num_visited, drone_at_oxygen_generator, 0);
printf("Pt 2: %d\n", m);
free_program_instance(drone_at_oxygen_generator);
free(source);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment