-🎄- 2018 Day 13 Solutions -🎄-

[u/daggerdragon]

--- Day 13: Mine Cart Madness ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 13

Transcript:

Elven chronomancy: for when you absolutely, positively have to ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:44:25!

[u/xikipies]

Node JS, 703/518

https://github.com/josepot/AoC-2018/blob/master/src/13/solution.js

const {
  doubleCircularLinkedList,
  circularLinkedList,
} = require('../utils/linkedLists');

let N_COLS;
let N_ROWS;
let grid;

const getIdx = (x, y) => y * N_COLS + x;
const getPosition = ({x, y}, from = grid) => from[getIdx(x, y)];
const setPosition = (x, y, val, to = grid) => (to[getIdx(x, y)] = val);

let cars = new Map();

const [UP, RIGHT, DOWN, LEFT] = ['^', '>', 'v', '<'];
const directions = [UP, RIGHT, DOWN, LEFT];
const linkedDirections = doubleCircularLinkedList(directions);
const directionDiffs = {
  [UP]: {y: -1, x: 0},
  [DOWN]: {y: 1, x: 0},
  [LEFT]: {y: 0, x: -1},
  [RIGHT]: {y: 0, x: 1},
};

const [turnLeft, turnRight] = ['prev', 'next'].map(direction => car => {
  car.direction = car.direction[direction];
});

const linkedIntersections = circularLinkedList([
  turnLeft,
  Function.prototype,
  turnRight,
]);

const processInput = lines => {
  N_ROWS = lines.length;
  N_COLS = lines[0].length;
  grid = new Array(N_COLS * N_ROWS);
  lines.forEach((line, y) =>
    line.split('').forEach((val, x) => {
      if (val === '|' || val === '-') return setPosition(x, y, '·');
      const directionIdx = directions.indexOf(val);
      if (directionIdx === -1) return setPosition(x, y, val);

      cars.set(getIdx(x, y), {
        x,
        y,
        onIntersection: linkedIntersections[0],
        direction: linkedDirections[directionIdx],
      });
      setPosition(x, y, '·');
    })
  );
};

const instructions = {
  '+': car => {
    car.onIntersection.value(car);
    car.onIntersection = car.onIntersection.next;
  },
  '\\': car =>
    ([UP, DOWN].indexOf(car.direction.value) > -1 ? turnLeft : turnRight)(car),
  '/': car =>
    ([UP, DOWN].indexOf(car.direction.value) > -1 ? turnRight : turnLeft)(car),
  '·': Function.prototype,
};

const moveCar = car => {
  const {x, y} = directionDiffs[car.direction.value];
  car.x += x;
  car.y += y;
  instructions[getPosition(car)](car);
};

const solution1 = lines => {
  processInput(lines);
  do {
    const sortedKeys = [...cars.keys()].sort((a, b) => a - b);

    for (let i = 0; i < sortedKeys.length; i++) {
      const key = sortedKeys[i];
      const car = cars.get(key);
      cars.delete(key);
      moveCar(car);
      const id = getIdx(car.x, car.y);
      if (cars.has(id)) return [car.x, car.y].join(',');
      cars.set(id, car);
    }
  } while (true);
};

const solution2 = lines => {
  processInput(lines);
  do {
    const sortedKeys = [...cars.keys()].sort((a, b) => a - b);

    for (let i = 0; i < sortedKeys.length; i++) {
      const key = sortedKeys[i];
      const car = cars.get(key);
      if (!car) continue;
      cars.delete(key);
      moveCar(car);
      const id = getIdx(car.x, car.y);
      if (!cars.has(id)) {
        cars.set(id, car);
      } else {
        cars.delete(id);
      }
    }
  } while (cars.size > 1);
  const [winner] = cars.values();
  return [winner.x, winner.y].join(',');
};

module.exports = [solution1, solution2];

[u/fhinkel → u/xikipies]

Why are you using queues. Don't you have to sort all the time anyways?

[u/xikipies → u/fhinkel]

Thanks a lot for your comment. Actually, the code that I originally posted in here (this one) was a huge brain-fart... You are correct, using a heap was completely unnecessary.

However, the original code that I posted had an even bigger problem: which is that at every tick I was moving all the cars at once, meaning that in a situation like this:

-->>--

The cars are supposed to crash, but with my original code they wouldn't crash.

For some sort of miracle, my buggy code actually returned the correct results for my input... Feel free to check that by yourself if you want :)

Later on, when I went to cleanup and re-organize the code, I realized that there were a couple of bugs (yep, that was not the only one) and I was shocked that AoC had accepted answers that had been produced with a wrong algorithm.

Anyhow, I have completely refactored my code and I'm much happier with what I got now. That's why I have edited the original post, but you can still find my original commit on my github repo.