Discussion on: Advent of Code 2019 Solution Megathread - Day 15: Oxygen System

[Massimo Artizzu]

IntCodes on odd days as usual. Will we have to use them on Christmas too? 🤔

At first was considering getting the map out of the input itself, but it's hidden well enough so I thought it was easier to give it a try anyway.

So, the approach. Instead of the suggested way of backtracking with the drone, I decided to keep a "frontier" of tiles next to unexplored ones, and expand it at every iteration until the leak is reached (for part one) or the frontier is empty (for part two).

Therefor "frontier" consists in an object mapping coordinates with the "state" of the machine (which has to be copied). The only optimization I made here to my IntCode machine was using a Uint16Array instead of a normal array, but it wasn't really necessary.

To the code (in JavaScript):

// Initial part like usual, only using typed arrays. See my repo
function moveRobot(column, row, direction) {
  switch (direction) {
    case 1: return [ column, row - 1 ];
    case 2: return [ column, row + 1 ];
    case 3: return [ column - 1, row ];
    case 4: return [ column + 1, row ];
  }
}

function evolveFrontier(initialMap, initialState, condition) {
  const map = { ...initialMap };
  let frontier = { [Object.keys(map)[0]]: initialState };
  let counter = 0;
  while (!(condition(map, frontier))) {
    counter++;
    const newFrontier = {};
    for (const [ coords, state ] of Object.entries(frontier)) {
      const [ column, row ] = coords.split(',').map(Number);
      for (let direction = 1; direction <= 4; direction++) {
        const [ newColumn, newRow ] = moveRobot(column, row, direction);
        const positionKey = `${newColumn},${newRow}`;
        if (positionKey in map) {
          continue;
        }
        const newState = state.slice();
        const drone = createProgramInstance(newState, direction);
        const { value } = drone.next();
        map[positionKey] = value;
        if (value !== 0) {
          newFrontier[positionKey] = newState;
        }
        drone.return(); // Closes the generator to avoid memory leaks
      }
    }
    frontier = newFrontier;
  }
  return [ map, frontier, counter ];
}

The evolveFrontier function takes three arguments:

• the initial map (an object mapping coordinates with their type of tile): it's needed to keep track of the explored tiles;
• the initial state: a copy of the IntCode program;
• a condition callback: so the look knows when to stop. It return the map at the moment the condition becomes true; the frontier at the same istant; and the number of iterations.

The first part is now rather easy:

const [ tankMap, tankFrontier, movements ] = evolveFrontier(
  { '0,0': 1 },
  codes,
  map => [ ...Object.values(map) ].includes(2)
);
console.log('Part 1:', movements);

The values tankMap and tankFrontier will be needed for the second part:

const leakCoords = Object.keys(tankMap).find(coords => tankMap[coords] === 2);
const leakState = tankFrontier[leakCoords];

const [ ,, fillUpAfter ] = evolveFrontier(
  { [leakCoords]: 2 },
  leakState,
  (_, frontier) => Object.keys(frontier).length === 0
);
// -1 because the last round has always hit a wall
console.log('Part 2:', fillUpAfter - 1);

Find today's text, my input the my complete solution at my repo.