Created
December 17, 2019 21:48
-
-
Save FelicitusNeko/62d02b11c1ed7093ccd3c2c601cd09c8 to your computer and use it in GitHub Desktop.
Advent of Code 2019 Day 15
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const fs = require('fs'); | |
| const DIR_NORTH = 1, DIR_SOUTH = 2, DIR_WEST = 3, DIR_EAST = 4; | |
| const TURN_LEFT = 0, TURN_NO = 1, TURN_RIGHT = 2, TURN_BACK = 3; | |
| const STAT_WALL = 0, STAT_STEP = 1, STAT_OXY = 2; | |
| const MAP_WALL = 0, MAP_OPEN = 1, MAP_FINISH = 2, MAP_START = 3, MAP_LHR = 4, MAP_RHR = 5, MAP_BOTH = 6; | |
| class IntOpcodeMachine { | |
| constructor(pgm) { | |
| this.pgm = pgm.split(',').map(i => parseInt(i)); | |
| this.originalPgm = this.pgm.slice(0); | |
| this.position = 0; | |
| this.relBase = 0; | |
| this.cmdSize = { 1: 4, 2: 4, 3: 2, 4: 2, 5: 3, 6: 3, 7: 4, 8: 4, 9: 2, 99: 1 } | |
| this.input = []; this.output = []; | |
| } | |
| run() { | |
| let isRunning = true; | |
| let retval = true; | |
| let runCount = 0; | |
| while (isRunning && this.position < this.pgm.length) { | |
| let noun = 0, verb = 0; | |
| let opcode = this.pgm[this.position] % 100; | |
| if (this.cmdSize[opcode] === undefined) throw new Error(`Invalid opcode ${opcode} at position ${this.position}`); | |
| let mode = []; | |
| for (let x = 2; x <= this.cmdSize[opcode]; x++) mode.push(Math.round(this.pgm[this.position] / Math.pow(10, x)) % 10); | |
| switch (opcode) { | |
| case 1: // Add values | |
| noun = this.getWithMode(this.position + 1, mode[0]); | |
| verb = this.getWithMode(this.position + 2, mode[1]); | |
| this.setWithMode(this.position + 3, mode[2], noun + verb); | |
| break; | |
| case 2: // Multiply values | |
| noun = this.getWithMode(this.position + 1, mode[0]); | |
| verb = this.getWithMode(this.position + 2, mode[1]); | |
| this.setWithMode(this.position + 3, mode[2], noun * verb); | |
| break; | |
| case 3: // Get from input stack | |
| if (this.input.length === 0) return false; | |
| this.setWithMode(this.position + 1, mode[0], this.input.shift()); | |
| break; | |
| case 4: // Push to output stack | |
| this.output.push(this.getWithMode(this.position + 1, mode[0])); | |
| break; | |
| case 5: // Jump if true | |
| if (this.getWithMode(this.position + 1, mode[0]) !== 0) this.position = this.getWithMode(this.position + 2, mode[1]) - 3; | |
| break; | |
| case 6: // Jump if false | |
| if (this.getWithMode(this.position + 1, mode[0]) === 0) this.position = this.getWithMode(this.position + 2, mode[1]) - 3; | |
| break; | |
| case 7: // Evaluate less than | |
| this.setWithMode(this.position + 3, mode[2], (this.getWithMode(this.position + 1, mode[0]) < this.getWithMode(this.position + 2, mode[1]) ? 1 : 0)); | |
| break; | |
| case 8: // Evaluate equal | |
| this.setWithMode(this.position + 3, mode[2], (this.getWithMode(this.position + 1, mode[0]) === this.getWithMode(this.position + 2, mode[1]) ? 1 : 0)); | |
| break; | |
| case 9: // Adjust relative base | |
| this.relBase += this.getWithMode(this.position + 1, mode[0]); | |
| break; | |
| case 99: // End program | |
| isRunning = false; break; | |
| default: throw new Error(`Invalid opcode ${opcode} at position ${this.position}`); | |
| } | |
| this.position += this.cmdSize[opcode]; | |
| if (runCount > 50000) { | |
| console.debug(this.output); | |
| console.debug(this.toString()); | |
| throw new Error('Run length cap exceeded'); | |
| } | |
| } | |
| return retval; | |
| } | |
| addInput(data) { | |
| if (Array.isArray(data)) this.input = this.input.concat(data); | |
| else this.input.push(data); | |
| } | |
| getOutput() { return this.output.shift(); } | |
| getAllOutput() { | |
| let retval = this.output; | |
| this.output = []; | |
| return retval; | |
| } | |
| zeroFillToPos(pos) { | |
| while (this.pgm.length <= pos) this.pgm.push(0); | |
| } | |
| setAt(pos, data) { | |
| this.zeroFillToPos(pos); | |
| this.pgm[pos] = data; | |
| } | |
| getAt(pos) { | |
| this.zeroFillToPos(pos); | |
| return this.pgm[pos]; | |
| } | |
| getModePos(pos, mode) { | |
| switch (mode) { | |
| case 0: return this.pgm[pos]; | |
| case 1: return pos; | |
| case 2: return this.pgm[pos] + this.relBase; | |
| default: throw new Error(`Invalid access mode #${mode}`); | |
| } | |
| } | |
| setWithMode(pos, mode, data) { | |
| let modePos = this.getModePos(pos, mode); | |
| this.zeroFillToPos(modePos); | |
| this.pgm[modePos] = data; | |
| } | |
| getWithMode(pos, mode) { | |
| let modePos = this.getModePos(pos, mode); | |
| this.zeroFillToPos(modePos); | |
| return this.pgm[modePos]; | |
| } | |
| goto(pos) { this.position = pos; } | |
| restart() { this.pgm = this.originalPgm.slice(); this.position = 0; this.input = []; this.output = []; } | |
| toString() { return this.pgm.join(','); } | |
| } | |
| const turn = (turnType, curDir) => { | |
| switch (turnType) { | |
| case TURN_NO: return curDir; | |
| case TURN_LEFT: switch (curDir) { | |
| case DIR_NORTH: case DIR_SOUTH: return curDir + 2; | |
| case DIR_WEST: return DIR_SOUTH; | |
| case DIR_EAST: return DIR_NORTH; | |
| } | |
| case TURN_RIGHT: switch (curDir) { | |
| case DIR_NORTH: return DIR_EAST; | |
| case DIR_SOUTH: return DIR_WEST; | |
| case DIR_WEST: case DIR_EAST: return curDir - 2; | |
| } | |
| case TURN_BACK: switch (curDir) { | |
| case DIR_NORTH: case DIR_WEST: return curDir + 1; | |
| case DIR_SOUTH: case DIR_EAST: return curDir - 1; | |
| } | |
| } | |
| } | |
| const posAt = (X, Y, dir) => { | |
| switch (dir) { | |
| case DIR_NORTH: return [X, Y - 1]; | |
| case DIR_SOUTH: return [X, Y + 1]; | |
| case DIR_WEST: return [X - 1, Y]; | |
| case DIR_EAST: return [X + 1, Y]; | |
| } | |
| } | |
| let bigData = fs.readFileSync('day15.txt').toString(); | |
| let machine = new IntOpcodeMachine(bigData); | |
| let mapData = { '0,0': 3 }; | |
| for (let turnMode = 0; turnMode < 2; turnMode++) { | |
| machine.restart(); | |
| let curDir = DIR_NORTH, lastDir = DIR_NORTH, curTurn = turnMode ? 6 : 0, lastOutput = -1; | |
| let X = 0, Y = 0; | |
| while (lastOutput != STAT_OXY) { | |
| lastDir = turn(curTurn % 4, curDir); | |
| machine.addInput(lastDir); | |
| machine.run(); | |
| lastOutput = machine.getOutput(); | |
| newPos = posAt(X, Y, lastDir); | |
| if (lastOutput === 1) { | |
| if ((mapData[newPos.join(',')] === 4 && turnMode === 1) || mapData[newPos.join(',')] === 6) mapData[newPos.join(',')] = 6; | |
| else mapData[newPos.join(',')] = turnMode + 4; | |
| } | |
| else mapData[newPos.join(',')] = lastOutput; | |
| if (lastOutput === STAT_WALL) turnMode ? curTurn-- : curTurn++; | |
| else { | |
| [X, Y] = newPos; | |
| curTurn = turnMode ? 6 : 0; | |
| curDir = lastDir; | |
| } | |
| } | |
| } | |
| mapData['0,0'] = 3; | |
| let offsetX = Number.MAX_SAFE_INTEGER, offsetY = Number.MAX_SAFE_INTEGER, maxX = Number.MIN_SAFE_INTEGER, maxY = Number.MIN_SAFE_INTEGER; | |
| for (let coords in mapData) { | |
| let coordNum = coords.split(',').map(i => parseInt(i)); | |
| offsetX = Math.min(coordNum[0], offsetX); offsetY = Math.min(coordNum[1], offsetY); | |
| maxX = Math.max(coordNum[0], maxX); maxY = Math.max(coordNum[1], maxY); | |
| } | |
| let mapImage = [], solutionSteps = 0; | |
| for (let buildY = offsetY; buildY <= maxY; buildY++) { | |
| let row = []; | |
| for (let buildX = offsetX; buildX <= maxX; buildX++) { | |
| switch (mapData[`${buildX},${buildY}`]) { | |
| case MAP_WALL: row.push('#'); break; | |
| case MAP_OPEN: row.push('.'); break; | |
| case MAP_FINISH: row.push('F'); solutionSteps++; break; | |
| case MAP_START: row.push('S'); break; | |
| case MAP_LHR: row.push(','); break; | |
| case MAP_RHR: row.push('\''); break; | |
| case MAP_BOTH: row.push('+'); solutionSteps++; break; | |
| default: row.push(' '); break; | |
| } | |
| } | |
| mapImage.push(row); | |
| } | |
| console.log(mapImage.map(i => i.join('')).join('\n'), solutionSteps); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const fs = require('fs'); | |
| const DIR_NORTH = 1, DIR_SOUTH = 2, DIR_WEST = 3, DIR_EAST = 4; | |
| const TURN_LEFT = 0, TURN_NO = 1, TURN_RIGHT = 2, TURN_BACK = 3; | |
| const STAT_WALL = 0, STAT_STEP = 1, STAT_OXY = 2; | |
| const MAP_WALL = 0, MAP_OPEN = 1, MAP_OXY = 2, MAP_NEWOXY = 3; | |
| class IntOpcodeMachine { | |
| constructor(pgm) { | |
| this.pgm = pgm.split(',').map(i => parseInt(i)); | |
| this.originalPgm = this.pgm.slice(0); | |
| this.position = 0; | |
| this.relBase = 0; | |
| this.cmdSize = { 1: 4, 2: 4, 3: 2, 4: 2, 5: 3, 6: 3, 7: 4, 8: 4, 9: 2, 99: 1 } | |
| this.input = []; this.output = []; | |
| } | |
| run() { | |
| let isRunning = true; | |
| let retval = true; | |
| let runCount = 0; | |
| while (isRunning && this.position < this.pgm.length) { | |
| let noun = 0, verb = 0; | |
| let opcode = this.pgm[this.position] % 100; | |
| if (this.cmdSize[opcode] === undefined) throw new Error(`Invalid opcode ${opcode} at position ${this.position}`); | |
| let mode = []; | |
| for (let x = 2; x <= this.cmdSize[opcode]; x++) mode.push(Math.round(this.pgm[this.position] / Math.pow(10, x)) % 10); | |
| switch (opcode) { | |
| case 1: // Add values | |
| noun = this.getWithMode(this.position + 1, mode[0]); | |
| verb = this.getWithMode(this.position + 2, mode[1]); | |
| this.setWithMode(this.position + 3, mode[2], noun + verb); | |
| break; | |
| case 2: // Multiply values | |
| noun = this.getWithMode(this.position + 1, mode[0]); | |
| verb = this.getWithMode(this.position + 2, mode[1]); | |
| this.setWithMode(this.position + 3, mode[2], noun * verb); | |
| break; | |
| case 3: // Get from input stack | |
| if (this.input.length === 0) return false; | |
| this.setWithMode(this.position + 1, mode[0], this.input.shift()); | |
| break; | |
| case 4: // Push to output stack | |
| this.output.push(this.getWithMode(this.position + 1, mode[0])); | |
| break; | |
| case 5: // Jump if true | |
| if (this.getWithMode(this.position + 1, mode[0]) !== 0) this.position = this.getWithMode(this.position + 2, mode[1]) - 3; | |
| break; | |
| case 6: // Jump if false | |
| if (this.getWithMode(this.position + 1, mode[0]) === 0) this.position = this.getWithMode(this.position + 2, mode[1]) - 3; | |
| break; | |
| case 7: // Evaluate less than | |
| this.setWithMode(this.position + 3, mode[2], (this.getWithMode(this.position + 1, mode[0]) < this.getWithMode(this.position + 2, mode[1]) ? 1 : 0)); | |
| break; | |
| case 8: // Evaluate equal | |
| this.setWithMode(this.position + 3, mode[2], (this.getWithMode(this.position + 1, mode[0]) === this.getWithMode(this.position + 2, mode[1]) ? 1 : 0)); | |
| break; | |
| case 9: // Adjust relative base | |
| this.relBase += this.getWithMode(this.position + 1, mode[0]); | |
| break; | |
| case 99: // End program | |
| isRunning = false; break; | |
| default: throw new Error(`Invalid opcode ${opcode} at position ${this.position}`); | |
| } | |
| this.position += this.cmdSize[opcode]; | |
| if (runCount > 50000) { | |
| console.debug(this.output); | |
| console.debug(this.toString()); | |
| throw new Error('Run length cap exceeded'); | |
| } | |
| } | |
| return retval; | |
| } | |
| addInput(data) { | |
| if (Array.isArray(data)) this.input = this.input.concat(data); | |
| else this.input.push(data); | |
| } | |
| getOutput() { return this.output.shift(); } | |
| getAllOutput() { | |
| let retval = this.output; | |
| this.output = []; | |
| return retval; | |
| } | |
| zeroFillToPos(pos) { | |
| while (this.pgm.length <= pos) this.pgm.push(0); | |
| } | |
| setAt(pos, data) { | |
| this.zeroFillToPos(pos); | |
| this.pgm[pos] = data; | |
| } | |
| getAt(pos) { | |
| this.zeroFillToPos(pos); | |
| return this.pgm[pos]; | |
| } | |
| getModePos(pos, mode) { | |
| switch (mode) { | |
| case 0: return this.pgm[pos]; | |
| case 1: return pos; | |
| case 2: return this.pgm[pos] + this.relBase; | |
| default: throw new Error(`Invalid access mode #${mode}`); | |
| } | |
| } | |
| setWithMode(pos, mode, data) { | |
| let modePos = this.getModePos(pos, mode); | |
| this.zeroFillToPos(modePos); | |
| this.pgm[modePos] = data; | |
| } | |
| getWithMode(pos, mode) { | |
| let modePos = this.getModePos(pos, mode); | |
| this.zeroFillToPos(modePos); | |
| return this.pgm[modePos]; | |
| } | |
| goto(pos) { this.position = pos; } | |
| restart() { this.pgm = this.originalPgm.slice(); this.position = 0; this.input = []; this.output = []; } | |
| toString() { return this.pgm.join(','); } | |
| } | |
| const turn = (turnType, curDir) => { | |
| switch (turnType) { | |
| case TURN_NO: return curDir; | |
| case TURN_LEFT: switch (curDir) { | |
| case DIR_NORTH: case DIR_SOUTH: return curDir + 2; | |
| case DIR_WEST: return DIR_SOUTH; | |
| case DIR_EAST: return DIR_NORTH; | |
| } | |
| case TURN_RIGHT: switch (curDir) { | |
| case DIR_NORTH: return DIR_EAST; | |
| case DIR_SOUTH: return DIR_WEST; | |
| case DIR_WEST: case DIR_EAST: return curDir - 2; | |
| } | |
| case TURN_BACK: switch (curDir) { | |
| case DIR_NORTH: case DIR_WEST: return curDir + 1; | |
| case DIR_SOUTH: case DIR_EAST: return curDir - 1; | |
| } | |
| } | |
| } | |
| const posAt = (X, Y, dir) => { | |
| switch (dir) { | |
| case DIR_NORTH: return [X, Y - 1]; | |
| case DIR_SOUTH: return [X, Y + 1]; | |
| case DIR_WEST: return [X - 1, Y]; | |
| case DIR_EAST: return [X + 1, Y]; | |
| } | |
| } | |
| let bigData = fs.readFileSync('day15.txt').toString(); | |
| let machine = new IntOpcodeMachine(bigData); | |
| let mapData = { '0,0': 1 }; | |
| for (let turnMode = 0; turnMode < 2; turnMode++) { | |
| machine.restart(); | |
| let curDir = DIR_NORTH, lastDir = DIR_NORTH, curTurn = turnMode ? 6 : 0, lastOutput = -1; | |
| let X = 0, Y = 0; | |
| while (lastOutput != STAT_OXY) { | |
| lastDir = turn(curTurn % 4, curDir); | |
| machine.addInput(lastDir); | |
| machine.run(); | |
| lastOutput = machine.getOutput(); | |
| newPos = posAt(X, Y, lastDir); | |
| mapData[newPos.join(',')] = lastOutput; | |
| if (lastOutput === STAT_WALL) turnMode ? curTurn-- : curTurn++; | |
| else { | |
| [X, Y] = newPos; | |
| curTurn = turnMode ? 6 : 0; | |
| curDir = lastDir; | |
| } | |
| } | |
| } | |
| let offsetX = Number.MAX_SAFE_INTEGER, offsetY = Number.MAX_SAFE_INTEGER, maxX = Number.MIN_SAFE_INTEGER, maxY = Number.MIN_SAFE_INTEGER; | |
| for (let coords in mapData) { | |
| let coordNum = coords.split(',').map(i => parseInt(i)); | |
| offsetX = Math.min(coordNum[0], offsetX); offsetY = Math.min(coordNum[1], offsetY); | |
| maxX = Math.max(coordNum[0], maxX); maxY = Math.max(coordNum[1], maxY); | |
| } | |
| let map = []; | |
| for (let buildY = offsetY; buildY <= maxY; buildY++) { | |
| let row = []; | |
| for (let buildX = offsetX; buildX <= maxX; buildX++) { | |
| if (mapData[`${buildX},${buildY}`] === undefined) row.push(0); | |
| else row.push(mapData[`${buildX},${buildY}`]); | |
| } | |
| map.push(row); | |
| } | |
| maxX -= offsetX; maxY -= offsetY; | |
| let minutesToFull = 0, anyVacuumLeft = true; | |
| const drawMap = map => { | |
| return map.map(i => i.join('')).join('\n') | |
| .replace(/0/g, '#') | |
| .replace(/1/g, '.') | |
| .replace(/2/g, 'O'); | |
| } | |
| while (anyVacuumLeft) { | |
| anyVacuumLeft = false; | |
| for (let Y = 0; Y < map.length; Y++) { | |
| for (let X = 0; X < map[Y].length; X++) { | |
| if (map[Y][X] !== MAP_OPEN) continue; | |
| if (X > 0 && map[Y][X - 1] === MAP_OXY) { map[Y][X] = MAP_NEWOXY; continue; } | |
| else if (Y > 0 && map[Y - 1][X] === MAP_OXY) { map[Y][X] = MAP_NEWOXY; continue; } | |
| else if (X < maxX && map[Y][X + 1] === MAP_OXY) { map[Y][X] = MAP_NEWOXY; continue; } | |
| else if (Y < maxY && map[Y + 1][X] === MAP_OXY) { map[Y][X] = MAP_NEWOXY; continue; } | |
| else anyVacuumLeft = true; | |
| } | |
| } | |
| for (let Y = 0; Y < map.length; Y++) for (let X = 0; X < map[Y].length; X++) | |
| if (map[Y][X] === MAP_NEWOXY) map[Y][X] = MAP_OXY; | |
| minutesToFull++; | |
| } | |
| console.log(drawMap(map), minutesToFull); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment