2018/Day16/Day16B.c

204 lines
6.0 KiB
C
Raw Permalink Normal View History

2018-12-16 19:33:22 +00:00
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <assert.h>
typedef struct {
uint8_t opcode;
uint32_t a, b, c;
} Instruction;
typedef struct {
uint32_t before[4];
Instruction instruction;
uint32_t after[4];
} Sample;
enum {
2018-12-18 14:07:03 +00:00
ADDR, ADDI, MULR, MULI, BANR, BANI, BORR, BORI,
SETR, SETI, GTIR, GTRI, GTRR, EQIR, EQRI, EQRR,
2018-12-16 19:33:22 +00:00
};
2018-12-18 14:07:03 +00:00
#ifdef DEBUG
2018-12-16 19:33:22 +00:00
const char *names[] = {
2018-12-18 14:07:03 +00:00
"addr", "addi", "mulr", "muli", "banr", "bani", "borr", "bori",
"setr", "seti", "gtir", "gtri", "gtrr", "eqir", "eqri", "eqrr",
2018-12-16 19:33:22 +00:00
};
2018-12-18 14:07:03 +00:00
#endif
2018-12-16 19:33:22 +00:00
int opcodes[16];
int sample_read(Sample *s, FILE *file) {
int read = 0;
2018-12-18 14:07:03 +00:00
read = fscanf(file, "Before: [%u, %u, %u, %u]\n",
&s->before[0], &s->before[1], &s->before[2], &s->before[3]);
2018-12-16 19:33:22 +00:00
if (read != 4) return 0;
Instruction *i = &s->instruction;
2018-12-18 14:07:03 +00:00
read = fscanf(file, "%" SCNu8 " %u %u %u\n", &i->opcode, &i->a, &i->b, &i->c);
2018-12-16 19:33:22 +00:00
if (read != 4) return 0;
2018-12-18 14:07:03 +00:00
read = fscanf(file, "After: [%u, %u, %u, %u]\n\n",
&s->after[0], &s->after[1], &s->after[2], &s->after[3]);
2018-12-16 19:33:22 +00:00
if (read != 4) return 0;
return 1;
}
uint16_t sample_possible_opcodes(const Sample s) {
uint16_t possible_opcodes = 0;
Instruction i = s.instruction;
2018-12-18 14:07:03 +00:00
2018-12-16 19:33:22 +00:00
// Addition
if (s.after[i.c] == s.before[i.a] + s.before[i.b]) possible_opcodes |= 1 << ADDR;
if (s.after[i.c] == s.before[i.a] + i.b) possible_opcodes |= 1 << ADDI;
2018-12-18 14:07:03 +00:00
2018-12-16 19:33:22 +00:00
// Multiplication
if (s.after[i.c] == s.before[i.a] * s.before[i.b]) possible_opcodes |= 1 << MULR;
if (s.after[i.c] == s.before[i.a] * i.b) possible_opcodes |= 1 << MULI;
2018-12-18 14:07:03 +00:00
2018-12-16 19:33:22 +00:00
// Bitwise AND
if (s.after[i.c] == (s.before[i.a] & s.before[i.b])) possible_opcodes |= 1 << BANR;
if (s.after[i.c] == (s.before[i.a] & i.b)) possible_opcodes |= 1 << BANI;
2018-12-18 14:07:03 +00:00
2018-12-16 19:33:22 +00:00
// Bitwise OR
if (s.after[i.c] == (s.before[i.a] | s.before[i.b])) possible_opcodes |= 1 << BORR;
if (s.after[i.c] == (s.before[i.a] | i.b)) possible_opcodes |= 1 << BORI;
2018-12-18 14:07:03 +00:00
2018-12-16 19:33:22 +00:00
// Assignment
if (s.after[i.c] == s.before[i.a]) possible_opcodes |= 1 << SETR;
if (s.after[i.c] == i.a) possible_opcodes |= 1 << SETI;
2018-12-18 14:07:03 +00:00
2018-12-16 19:33:22 +00:00
// Greater-than testing
if (s.after[i.c] == (i.a > s.before[i.b])) possible_opcodes |= 1 << GTIR;
if (s.after[i.c] == (s.before[i.a] > i.b)) possible_opcodes |= 1 << GTRI;
if (s.after[i.c] == (s.before[i.a] > s.before[i.b])) possible_opcodes |= 1 << GTRR;
2018-12-18 14:07:03 +00:00
2018-12-16 19:33:22 +00:00
// Equality testing
if (s.after[i.c] == (i.a == s.before[i.b])) possible_opcodes |= 1 << EQIR;
if (s.after[i.c] == (s.before[i.a] == i.b)) possible_opcodes |= 1 << EQRI;
if (s.after[i.c] == (s.before[i.a] == s.before[i.b])) possible_opcodes |= 1 << EQRR;
return possible_opcodes;
}
int bits_set(uint16_t n) {
int bit = -1;
for (int i = 0; i < 16; i++) {
if ((n >> i) & 1) {
if (bit != -1) return -1;
bit = i;
}
}
return bit;
}
2018-12-18 14:07:03 +00:00
void find_opcodes(FILE *file) {
2018-12-16 19:33:22 +00:00
int unknown = 16;
2018-12-18 14:07:03 +00:00
uint16_t table[16] = {
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
};
Sample sample;
while (sample_read(&sample, file)) {
uint16_t possible_opcodes = sample_possible_opcodes(sample);
table[sample.instruction.opcode] &= possible_opcodes;
}
2018-12-16 19:33:22 +00:00
while (unknown > 0) {
for (int opcode = 0; opcode < 16; opcode++) {
int bit = bits_set(table[opcode]);
if (bit == -1) continue;
// Set every row in this column to 0
for (int j = 0; j < 16; j++)
table[j] &= ~(1 << bit);
opcodes[opcode] = bit;
unknown -= 1;
}
}
2018-12-18 14:07:03 +00:00
#ifdef DEBUG
for (int i = 0; i < 16; i++)
2018-12-16 19:33:22 +00:00
printf("%d: %s\n", i, names[opcodes[i]]);
2018-12-18 14:07:03 +00:00
#endif
2018-12-16 19:33:22 +00:00
}
int instruction_read(Instruction *i, FILE *file) {
return fscanf(file, "%" SCNu8 " %u %u %u\n",
&i->opcode, &i->a, &i->b, &i->c) == 4;
}
void instruction_execute(const Instruction *i, uint32_t *r) {
switch (opcodes[i->opcode]) {
// Addition
case ADDR: r[i->c] = r[i->a] + r[i->b]; break;
case ADDI: r[i->c] = r[i->a] + i->b; break;
// Multiplication
case MULR: r[i->c] = r[i->a] * r[i->b]; break;
case MULI: r[i->c] = r[i->a] * i->b; break;
// Bitwise AND
case BANR: r[i->c] = (r[i->a] & r[i->b]); break;
case BANI: r[i->c] = (r[i->a] & i->b); break;
// Bitwise OR
case BORR: r[i->c] = (r[i->a] | r[i->b]); break;
case BORI: r[i->c] = (r[i->a] | i->b); break;
// Assignment
case SETR: r[i->c] = r[i->a]; break;
case SETI: r[i->c] = i->a; break;
// Greater-than testing
case GTIR: r[i->c] = (i->a > r[i->b]); break;
case GTRI: r[i->c] = (r[i->a] > i->b); break;
case GTRR: r[i->c] = (r[i->a] > r[i->b]); break;
// Equality testing
case EQIR: r[i->c] = (i->a == r[i->b]); break;
case EQRI: r[i->c] = (r[i->a] == i->b); break;
case EQRR: r[i->c] = (r[i->a] == r[i->b]); break;
default: assert(0);
}
}
int main(int argc, char **argv) {
if (argc != 2) {
printf("Usage: %s [input]\n", argv[0]);
return EXIT_FAILURE;
}
FILE *file = fopen(argv[1], "r");
2018-12-18 14:07:03 +00:00
find_opcodes(file);
2018-12-16 19:33:22 +00:00
uint32_t registers[4] = {0};
Instruction instruction = {0};
while (instruction_read(&instruction, file)) {
2018-12-18 14:07:03 +00:00
#ifdef DEBUG
2018-12-16 19:33:22 +00:00
const char *name = names[opcodes[instruction.opcode]];
printf("opcode: %2d (%s), a: %d, b: %d, c: %d\n", instruction.opcode,
name, instruction.a, instruction.b, instruction.c);
2018-12-18 14:07:03 +00:00
#endif
2018-12-16 19:33:22 +00:00
instruction_execute(&instruction, registers);
2018-12-18 14:07:03 +00:00
#ifdef DEBUG
2018-12-16 19:33:22 +00:00
printf("registers: %d %d %d %d\n", registers[0], registers[1],
registers[2], registers[3]);
2018-12-18 14:07:03 +00:00
#endif
2018-12-16 19:33:22 +00:00
}
fclose(file);
2018-12-18 14:07:03 +00:00
printf("%d\n", registers[0]);
2018-12-16 19:33:22 +00:00
return EXIT_SUCCESS;
}