AoC Day 13: Mine Cart Madness

Day 13 puts us just over halfway! Hopefully, you're sticking with it and able to keep up. If not, we've got a weekend coming up. 🎅

Today, we're predicting minecart crashes! You heard me right: the plants from yesterday have their own minecart infrastructure. And these minecarts are not well managed. We'll be parsing some pretty crazy ASCII art inputs and simulating these carts to figure out where they might run into issues.

There's a lot of moving pieces to this one. Good luck!

Comments

[Juan Manuel Gimeno]

A solution in python in which I have represented the tracks as an array of transformation functions on carts.

from collections import namedtuple

# Orientations
UP, RIGHT, DOWN, LEFT = range(4)

# Turning
TURN_LEFT, GO_STRAIGH, TURN_RIGHT = range(3)

def next(turn):
    return (turn + 1) % 3

Cart = namedtuple("Cart", "x, y, orientation, next_turn")

def out_of_lane(cart):
    raise Exception("out of lane", cart)

def horizontal(cart):
    if cart.orientation == RIGHT:
        return cart._replace(x=cart.x+1)
    elif cart.orientation == LEFT:
        return cart._replace(x=cart.x-1)
    else:
        raise Exception("moving %s in horizontal lane", "UP" if cart.orientation == UP else "DOWN")

def vertical(cart):
    if cart.orientation == DOWN:
        return cart._replace(y=cart.y+1)
    elif cart.orientation == UP:
        return cart._replace(y=cart.y-1)
    else:
        raise Exception("moving %s in vertical lane", "LEFT" if cart.orientation == LEFT else "RIGHT")

def diagonal(cart):
    if cart.orientation == UP:
        return cart._replace(y=cart.y-1, orientation=LEFT)
    elif cart.orientation == RIGHT:
        return cart._replace(x=cart.x+1, orientation=DOWN)
    elif cart.orientation == DOWN:
        return cart._replace(y=cart.y+1, orientation=RIGHT)
    else:
        return cart._replace(x=cart.x-1, orientation=UP)

def contra_diagonal(cart):
    if cart.orientation == UP:
        return cart._replace(y=cart.y-1, orientation=RIGHT)
    elif cart.orientation == RIGHT:
        return cart._replace(x=cart.x+1, orientation=UP)
    elif cart.orientation == DOWN:
        return cart._replace(y=cart.y+1, orientation=LEFT)
    else:
        return cart._replace(x=cart.x-1, orientation=DOWN)

next_orientation = { 
    UP : {
        TURN_LEFT : LEFT,
        TURN_RIGHT : RIGHT }, 
    RIGHT : {
        TURN_LEFT : UP,
        TURN_RIGHT : DOWN }, 
    DOWN : {
        TURN_LEFT : RIGHT,
        TURN_RIGHT : LEFT }, 
    LEFT : {
        TURN_LEFT : DOWN,
        TURN_RIGHT : UP }, 
    }

def crossing(cart):
    orientation = next_orientation[cart.orientation].get(cart.next_turn, cart.orientation)
    next_turn = next(cart.next_turn)
    if cart.orientation == UP:
        return cart._replace(y=cart.y-1, orientation=orientation, next_turn=next_turn)
    elif cart.orientation == RIGHT:
        return cart._replace(x=cart.x+1, orientation=orientation, next_turn=next_turn)
    elif cart.orientation == DOWN:
        return cart._replace(y=cart.y+1, orientation=orientation, next_turn=next_turn)
    else:
        return cart._replace(x=cart.x-1, orientation=orientation, next_turn=next_turn)

translate_orientation = { "^" : UP, ">" : RIGHT, "v" : DOWN, "<" : LEFT }

translate_cell = { " " : out_of_lane, 
                   "-" : horizontal, "<" : horizontal, ">" : horizontal,
                   "|" : vertical, "^" : vertical, "v" : vertical,
                   "/" : contra_diagonal, 
                   "\\" : diagonal,
                   "+" : crossing }

def parse_lines(file):
    return [line.rstrip("\n") for line in file if len(line) > 0]

def test_parse_lines_test1():
    with open("test1.txt", "r") as test1:
        expected = ['|', 'v', '|', '|', '|', '^', '|']
        assert expected == parse_lines(test1)

def test_parse_lines_test2():
    with open("test2.txt", "r") as test2:
        expected = ['/->-\\        ',
                    '|   |  /----\\',
                    '| /-+--+-\\  |',
                    '| | |  | v  |',
                    '\\-+-/  \\-+--/',
                    '  \\------/   ']
        assert expected == parse_lines(test2)

def parse_carts(lines):
    carts = []
    for y, row in enumerate(lines):
        for x, c in enumerate(row):
            if c in { '>', '<', '^', 'v' }:
                carts.append(Cart(x=x, y=y, orientation=translate_orientation[c], next_turn=0))
    return carts

def test_parse_carts_test1():
    with open("test1.txt", "r") as test1:
        expected = [Cart(x=0, y=1, orientation=DOWN, next_turn=0),
                    Cart(x=0, y=5, orientation=UP, next_turn=0)]
        assert expected == parse_carts(parse_lines(test1))

def test_parse_carts_test2():
    with open("test2.txt", "r") as test2:
        expected = [Cart(x=2, y=0, orientation=RIGHT, next_turn=0),
                    Cart(x=9, y=3, orientation=DOWN, next_turn=0)]
        assert expected == parse_carts(parse_lines(test2))

def parse_grid(lines):
    grid = []
    for line in lines:
        row = []
        for c in line:
            row.append(translate_cell[c])
        grid.append(row)
    return grid

def test_parse_grid_test1():
    with open("test1.txt", "r") as test1:
        expected = [[vertical]] * 7
        assert expected == parse_grid(parse_lines(test1))

def parse(fname):
    with open(fname, "r") as f:
        lines = parse_lines(f)
        carts = parse_carts(lines)
        grid = parse_grid(lines)
    return carts, grid

def move(cart, grid):
    if cart.orientation == UP:
        x, y = cart.x, cart.y-1
    elif cart.orientation == RIGHT:
        x, y = cart.x+1, cart.y
    elif cart.orientation == DOWN:
        x, y = cart.x, cart.y+1
    else:
        x, y = cart.x-1, cart.y
    return grid[y][x](cart)

def calc_part1(carts, grid):
    while True:
        carts.sort(key=lambda cart: (cart.y, cart.x))
        occupied_positions = { (cart.x, cart.y) for cart in carts }
        next_carts = []
        for cart in carts:
            occupied_positions.remove((cart.x, cart.y))
            new_cart = move(cart, grid)
            if (new_cart.x, new_cart.y) in occupied_positions:
                return (new_cart.x, new_cart.y)
            occupied_positions.add((new_cart.x, new_cart.y))
            next_carts.append(new_cart)
        carts = next_carts

def part1(fname):
    carts, grid = parse(fname)
    return calc_part1(carts, grid)

def test_part1():
    assert (0, 3) == part1("test1.txt")
    assert (7, 3) == part1("test2.txt")

def calc_part2(carts, grid):
    while True:
        if len(carts) == 1:
            return carts[0].x, carts[0].y
        carts.sort(key=lambda cart: (cart.y, cart.x))
        occupied_positions = { (cart.x, cart.y) for cart in carts }
        next_carts = []
        for cart in carts:
            if (cart.x, cart.y) not in occupied_positions:
                continue
            occupied_positions.remove((cart.x, cart.y))
            new_car = move(cart, grid)
            if (new_car.x, new_car.y) in occupied_positions:
                occupied_positions.remove((new_car.x, new_car.y))
            else:
                occupied_positions.add((new_car.x, new_car.y))
            next_carts.append(new_car)
        carts = [cart for cart in next_carts if (cart.x, cart.y) in occupied_positions]

def part2(fname):
    carts, grid = parse(fname)
    return calc_part2(carts, grid)

def test_part2():
    assert (6, 4) == part2("test3.txt")

if __name__ == "__main__":
    print("Part1", part1("input.txt"))
    print("Part2", part2("input.txt"))

[Neil Gall]

Really interesting how yours is very much the same concept as mine but Pythonic rather than Kotlin-ic!

github.com/neilgall/adventofcode20...

[Juan Manuel Gimeno]

One idea I want to explore (I don't know when) is to substitute most of the functions with dictionaries and func calls by lookups. I think this way I can represent the movements in a way similar to a rule system.

[Javid Asgarov]

Solution in javascript. Probably it can be done more pretty, I feel like I was way too explicit with every move, but it worked. I do this by opening the tab with input, opening dev tools and pasting the code right in the console xD.

(function() {
  let data = document
    .getElementsByTagName('pre')[0]
    .innerHTML.split('\n')
    .map(item => {
      return convertHTMLSymbols(item).split('');
    });

  function convertHTMLSymbols(str) {
    return str.replace(/&gt;/g, '>').replace(/&lt;/g, '<');
  }

  const backDirChange = {
    ['moves>']: 'v',
    ['moves<']: '^',
    ['movesv']: '>',
    ['moves^']: '<'
  };

  const forwDirChange = {
    ['moves>']: '^',
    ['moves<']: 'v',
    ['movesv']: '<',
    ['moves^']: '>'
  };

  const curves = [`\\`, `/`];

  const moveMe = {
    goRight(car) {
      car.position += 1;
      return car;
    },
    goLeft(car) {
      car.position -= 1;
      return car;
    },
    goUp(car) {
      car.row -= 1;
      return car;
    },
    goDown(car) {
      car.row += 1;
      return car;
    }
  };

  function shouldChangeDirection(car, data) {
    if (data[car.row] && data[car.row][car.position] === curves[0]) {
      car.moves = backDirChange[`moves${car.moves}`];
    } else if (data[car.row] && data[car.row][car.position] === curves[1]) {
      car.moves = forwDirChange[`moves${car.moves}`];
    }
  }

  function isAtIntersection(car) {
    if (car.nextIntersection === 'straight') {
      car.nextIntersection = 'right';
      return;
    }
    if (car.nextIntersection === 'left' && car.moves === 'v') {
      car.moves = '>';
      car.nextIntersection = 'straight';
    } else if (car.nextIntersection === 'right' && car.moves === 'v') {
      car.moves = '<';
      car.nextIntersection = 'left';
    } else if (car.nextIntersection === 'left' && car.moves === '^') {
      car.moves = '<';
      car.nextIntersection = 'straight';
    } else if (car.nextIntersection === 'right' && car.moves === '^') {
      car.moves = '>';
      car.nextIntersection = 'left';
    } else if (car.nextIntersection === 'left' && car.moves === '<') {
      car.moves = 'v';
      car.nextIntersection = 'straight';
    } else if (car.nextIntersection === 'right' && car.moves === '<') {
      car.moves = '^';
      car.nextIntersection = 'left';
    } else if (car.nextIntersection === 'left' && car.moves === '>') {
      car.moves = '^';
      car.nextIntersection = 'straight';
    } else if (car.nextIntersection === 'right' && car.moves === '>') {
      car.moves = 'v';
      car.nextIntersection = 'left';
    }
  }

  function makeMove(car, data) {
    if (car.moves === '<') {
      moveMe.goLeft(car);
    } else if (car.moves === '>') {
      moveMe.goRight(car);
    } else if (car.moves === 'v') {
      moveMe.goDown(car);
    } else if (car.moves === '^') {
      moveMe.goUp(car);
    }
    if (data[car.row][car.position] === '+') {
      isAtIntersection(car);
    } else {
      shouldChangeDirection(car, data);
    }
  }

  function carHasSameCoords(car, cars) {
    let result = false;
    cars.forEach(myCar => {
      if (myCar.crashed === true || myCar.crashed === true) {
        return;
      } else if (
        myCar.row === car.row &&
        car.position === myCar.position &&
        car.firstPosition !== myCar.firstPosition
      ) {
        car.crashed = true;
        myCar.crashed = true;
        result = true;
      }
    });
    return result;
  }

  function arrangeOrderOfMoves(cars) {
    return cars
      .sort((a, b) => {
        if (a.row === b.row) {
          return a.position - b.position;
        }
        return a.row - b.row;
      })
      .filter(car => car.crashed === false);
  }

  function howManyCartsLeft(cars) {
    let i = 0;
    let myCar;
    cars.forEach(car => {
      if (!car.crashed) {
        i += 1;
        myCar = car;
      }
    });
    return { number: i, car: myCar };
  }

  function findAnswer(data) {
    const carPositions = [];
    const carMoves = ['>', '<', '^', 'v'];
    data.forEach((row, yIndex) => {
      row.forEach((value, xIndex) => {
        if (carMoves.indexOf(value) !== -1) {
          carPositions.push({
            firstPosition: `${xIndex}, ${yIndex}`,
            row: yIndex,
            position: xIndex,
            moves: value,
            crashed: false,
            nextIntersection: 'left'
          });
        }
      });
    });
    let firstAnswer = [];
    let secondAnswer = [];
    for (let i = 0; i < 20000; i++) {
      arrangeOrderOfMoves(carPositions).forEach(car => {
        if (!car.crashed) {
          makeMove(car, data);
        }
        let check = carHasSameCoords(car, carPositions);
        if (check && firstAnswer.length === 0) {
          firstAnswer = [car.position, car.row];
        }
        let remaining = howManyCartsLeft(carPositions);
        if (remaining.number === 1) {
          secondAnswer = [remaining.car.position, remaining.car.row];
          i = Infinity;
        }
      });
    }
    console.log(firstAnswer, secondAnswer);
    return {
      firstAnswer,
      secondAnswer
    };
  }

  const answer = findAnswer(data);
})();

[Ali Spittel]

This.Was.Awful.

from copy import deepcopy

with open('input.txt', 'r') as f:
    grid = []
    for line in f:
        grid.append(list(line.replace('\n', '')))


increments = {
    '<': [-1, 0],
    '>': [1, 0],
    'v': [0, 1],
    '^': [0, -1]
}

intersections = {
    "left": {
        "v": ">",
        "^": "<",
        ">": "^",
        "<": "v"
    },
    "right": {
        "v": "<",
        "^": ">",
        ">": "v",
        "<": "^"
    }
}

curves = {
    "/": {
        "v": "<",
        "^": ">",
        ">": "^",
        "<": "v"
    },
    "\\": {
        "v": ">",
        "^": "<",
        ">": "v",
        "<": "^"
    }
}

directions = ["left", "straight", "right", "straight"]

def change_directions(direction):
    if direction == "left":
        return "straight"
    if direction == "right":
        return "left"
    if direction == "straight":
        return "right"

class Cart:
    def __init__(self, x, y, direction):
        self.x = x
        self.y = y
        self.direction = direction
        self.turn = "left"

    def __repr__(self):
        return f'x={self.x} y={self.y} direction={self.direction} turn={self.turn}'

    def move_straight(self):
        x_move, y_move = increments[self.direction]
        self.x += x_move
        self.y += y_move

    def intersection(self):
        if self.turn != "straight":
            self.direction = intersections[self.turn][self.direction]
        self.move_straight()
        self.turn = change_directions(self.turn)

    def curve(self, curve):
        self.direction = curves[curve][self.direction]
        self.move_straight()

    def coordinates(self):
        return f'{self.x},{self.y}'

    def move(self):
        move = grid[self.y][self.x]
        if move == "|" or move == "-":
            self.move_straight()
        elif move == "+":
            self.intersection()
        elif move == "/" or move == "\\":
            self.curve(move)
        else:
            print("whatthefuck")


carts = []
for y, row in enumerate(grid):
    for x, col in enumerate(row):
        if col in "<>v^":
            carts.append(Cart(x, y, col))


def clean_original(grid):
    for x, row in enumerate(grid):
        for y, col in enumerate(row):
            if col == ">" or col == "<":
                grid[x][y] = "-"
            elif col == "^" or col == "v":
                grid[x][y] = "|"
    return grid


def format_grid(grid):
    for cart in carts:
        grid[cart.y][cart.x] = cart.direction
    for row in grid:
        print(''.join(row))


def last_survivor(carts):
    while len(carts) > 1:
        seen = set(cart.coordinates() for cart in carts)
        for cart in carts:
            if cart.coordinates() in seen:
                seen.remove(cart.coordinates())
                cart.move()
                if cart.coordinates() in seen:
                    seen.remove(cart.coordinates())
                else:
                    seen.add(cart.coordinates())
        carts = [cart for cart in carts if cart.coordinates() in seen]
    return carts[0]


def get_collision(carts):
    seen = set()
    for cart in carts:
        cart.move()
        if (cart.x, cart.y,) in seen:
            return cart
        seen.add((cart.x, cart.y,))
    return get_collision(carts)

grid = clean_original(grid)
# 1
print(get_collision(deepcopy(carts)))
# 2
print(last_survivor(carts))

[E. Choroba]

I like the declarative section at the beginning (and used a similar one in my solution below).

[Viktors Jenovs]

I remember something similar form last years AoC :)

Today most of my bugs were from me not knowing PHP (I'm using AoC to learn it). After JS I just keep forgetting that arrays are passed by value and you need to use pointer (&) to pass variable by reference.

<?php
$input = require_once 'readFile.php';

function createGridAndCarts($input) {
  $carts = [];
  $grid = [];

  foreach ($input as $i => $str) {
    $str = preg_replace('/\n/', '', $str);
    $gridLine = str_split($str);
    $cart = [];
    $isCart = ['>' => '-', 'v' => '|', '<' => '-', '^' => '|'];

    foreach ($gridLine as $key => $value) {
      if (in_array($value, array_keys($isCart))) {
        $carts[] = ['y' => $i, 'x' => $key, 'pos' => $value, 'cross' => 'right'];
        $gridLine[$key] = $isCart[$value];
      }
      $grid[$i] = $gridLine;
    }
  }
  return [$grid, $carts];
}

function move($cart, $grid) {
  $turnR = ['^' => '>', '>' => 'v', 'v' => '<', '<' => '^'];
  $turnL = ['^' => '<', '>' => '^', 'v' => '>', '<' => 'v'];
  $nextCross = ['left' => 'straight', 'straight' => 'right', 'right' => 'left'];

  $currentPath = $grid[$cart['y']][$cart['x']];
  $newPos = $cartPos = $cart['pos'];
  $cartUpDown = $cartPos == '^' || $cartPos == 'v';
  $cartLeftRihgt = $cartPos == '>' || $cartPos == '<';

  if ($currentPath == '+') {
    $lastCross = $cart['cross'];
    $cart['cross'] = $nextCross[$lastCross];

    if ($lastCross == 'right') {
      $newPos = $turnL[$cart['pos']];
    } else if ($lastCross == 'straight') {
      $newPos = $turnR[$cart['pos']];
    }
  } else if ($currentPath == '\\') {
    $cartUpDown && $newPos = $turnL[$cartPos];
    $cartLeftRihgt && $newPos = $turnR[$cartPos];
  } else if ($currentPath == '/') {
    $cartUpDown && $newPos = $turnR[$cartPos];
    $cartLeftRihgt && $newPos = $turnL[$cartPos];
  }
  $cart['pos'] = $cartPos = $newPos;

  $cartPos == '>' && $cart['x']++;
  $cartPos == '<' && $cart['x']--;
  $cartPos == '^' && $cart['y']--;
  $cartPos == 'v' && $cart['y']++;

  return $cart;
}

function sortCarts($carts) {
  usort($carts, function($c1, $c2) {
    $sortY = $c1['y'] <=> $c2['y'];
    if ($sortY == 0) {
      return $c1['x'] <=> $c2['x'];
    }
    return $sortY;
  });
  return $carts;
}

function hasCollided($cart, $carts): bool {
  $collidors = 0;
  foreach ($carts as $c) {
    if ($cart['x'] == $c['x'] && $cart['y'] == $c['y']) {
      $collidors++;
    }
  }
  return  $collidors > 1;
}

function findCollisionId($carts, $ownId) {
  $cart = $carts[$ownId];
  foreach ($carts as $key => $val) {
    if ($key != $ownId && $cart['x'] == $val['x'] && $cart['y'] == $val['y']) {
      return $key;
    }
  }
  return NULL;
}

function findFirstCollision($grid, $carts) {
  $collision = false;

  while(!$collision) {
    foreach ($carts as $i => $cart) {
      $cart = move($cart, $grid);

      $carts[$i] = $cart;

      $collision = hasCollided($cart, $carts);
      if ($collision) {
        return $cart['x'] . "," . $cart['y'];
      }

    }
  }
}

function findLastCartStanding($grid, $carts) {
  while(count($carts) > 1) {
    foreach ($carts as $i => &$cart) {
      if ($cart == NULL) {
        continue;
      }

      $cart = move($cart, $grid);
      $carts[$i] = $cart;

      $collision = hasCollided($cart, $carts);
      if ($collision) {
        $id = findCollisionId($carts, $i);
        $carts[$id] = NULL;
        $carts[$i] = NULL;
      }
    }
    $carts = sortCarts(array_filter($carts));
  }
  return $carts[0];
}

[$grid, $carts] = createGridAndCarts($input);

echo "First collision at \t" . findFirstCollision($grid, $carts) . "\n";
$cart = findLastCartStanding($grid, $carts);
echo "Last cart stands at \t" . $cart['x'] . "," . $cart['y'] . "\n";
?>

readFile.php

<?php
$file = fopen("input.txt", "r") or exit("Unable to open file");

while(!feof($file)) {
  $array[] = fgets($file);
}

fclose($file);

return array_filter($array);
?>

[Neil Gall]

Half way, and we have a puzzle that just needs cranked through. There's no trick that particularly helps - just read the input into a big 2D array, turn the cart symbols into little models of the carts that can maintain the necessary information about the next turn, etc., and run the ticks.

It can be done without a bunch of ugly and error-prone mutable state though. First a model:

data class Pos(val x: Int, val y: Int)

enum class Dir { LEFT, RIGHT, UP, DOWN }

enum class Turn { LEFT, STRAIGHT, RIGHT }

data class Plan(val dir: Dir, val turn: Turn)

data class Cart(val id: Int, val pos: Pos, val plan: Plan, val collided: Boolean = false)

typealias Track = Char
typealias Tracks = List<CharArray>

data class Model(val tracks: Tracks, val carts: List<Cart>)

Loading the input data

The input text lines are just mapped to CharArrays. Then I use a pair of foldIndexed() calls run over the input on both axes and find the locations of the carts. A starting model for each cart is built here.

fun load(lines: List<String>): Model {
    val tracks: Tracks = lines.map(String::toCharArray)

    val carts: List<Cart> = tracks.foldIndexed(listOf<Cart>()) { y, carts, row ->
        row.foldIndexed(carts) { x, carts_, c ->
            if (!("^v<>".contains(c)))
                carts_
            else
                carts_ + Cart(carts_.size, Pos(x, y), Plan(dirFor(c), Turn.LEFT))
        }
    }

Finally I replace the cart positions with track characters. I could have left them in place and given the original characters the same semantics, I guess. No big deal.

    carts.forEach { c ->
        tracks[c.pos.y][c.pos.x] = (if (c.plan.dir == Dir.LEFT || c.plan.dir == Dir.RIGHT) '-' else '|')
    }

    return Model(tracks, carts)
}

Part 1

Cart movement is broken into a bunch of little functions, each of which should be pretty easy to understand.

fun Dir.turn(t: Turn): Dir = when(t) {
    Turn.STRAIGHT -> this
    Turn.LEFT -> when (this) {
        Dir.UP -> Dir.LEFT
        Dir.LEFT -> Dir.DOWN
        Dir.DOWN -> Dir.RIGHT
        Dir.RIGHT -> Dir.UP
    }
    Turn.RIGHT -> when (this) {
        Dir.UP -> Dir.RIGHT
        Dir.RIGHT -> Dir.DOWN
        Dir.DOWN -> Dir.LEFT
        Dir.LEFT -> Dir.UP
    }
}

fun Turn.next(): Turn = when(this) {
    Turn.LEFT -> Turn.STRAIGHT
    Turn.STRAIGHT -> Turn.RIGHT
    Turn.RIGHT -> Turn.LEFT
}

fun Pos.apply(plan: Plan): Pos = when(plan.dir) {
    Dir.UP -> Pos(x, y-1)
    Dir.DOWN -> Pos(x, y+1)
    Dir.LEFT -> Pos(x-1, y)
    Dir.RIGHT -> Pos(x+1, y)
}

The interesting one is Plan.adjust() which takes the current track character at a cart's position and builds a new plan for the cart. On intersections it applies turning logic, on curves it changes direction, etc. In some cases the plan doesn't change.

fun Plan.adjust(t: Track): Plan = when(t) {
    '+' -> Plan(dir.turn(turn), turn.next())
    '/' -> when (dir) {
        Dir.UP -> Plan(Dir.RIGHT, turn)
        Dir.RIGHT -> Plan(Dir.UP, turn)
        Dir.DOWN -> Plan(Dir.LEFT, turn)
        Dir.LEFT -> Plan(Dir.DOWN, turn)
    }
    '\\' -> when (dir) {
        Dir.UP -> Plan(Dir.LEFT, turn)
        Dir.LEFT -> Plan(Dir.UP, turn)
        Dir.DOWN -> Plan(Dir.RIGHT, turn)
        Dir.RIGHT -> Plan(Dir.DOWN, turn)
    }
    '-' -> this
    '|' -> this
    else -> throw IllegalStateException()
}

Moving a cart is a matter of determining the new plan based on the current track character, then executing the plan.

fun Cart.move(tracks: Tracks): Cart {
    val newPlan = plan.adjust(tracks[pos.y][pos.x])
    return Cart(id, pos.apply(newPlan), newPlan)
}

Scanning for the order to move the carts makes use of a nice Kotlin library feature of chainable comparators:

val scanOrder: Comparator<Cart> =
    Comparator<Cart> { 
        c1, c2 -> c1.pos.y - c2.pos.y
    }.then(Comparator<Cart> {
        c1, c2 -> c1.pos.x - c2.pos.x
    })

Each tick is implemented by moving the carts in scan order and checking for collisions. One tricky part of this is that the carts move one at a time, giving a bunch of inter-tick mini-states. So the initial state of the fold is the previous state's carts, and on each iteration of the fold one cart is replaced by its updated version. This ensures the correct collision comparisons are made.

A whole new model is built each time.

fun Cart.checkCollisions(carts: Collection<Cart>): Cart =
    if (carts.any { c -> c.collided })
        this // only want the first collision
    else if (carts.none { c -> c.pos == pos })
        this
    else
        this.copy(collided=true)

fun Model.tick(): Model {
    val newCarts = cartsInScanOrder.fold(carts) { carts_, c ->
        val otherCarts = carts_.filter { it != c }
        otherCarts + c.move(tracks).checkCollisions(otherCarts)
    }
    return Model(tracks, newCarts)
}

Running the simulation makes use of an infinite sequence of states I call the timeline:

fun timeline(initial: Model): Sequence<Model> {
    var model = initial
    return sequence {
        while (true) {
            yield(model)
            model = model.tick()
        }
    }
}

Just drop states from this sequence until a collision is detected, then find the crashed cart:

fun Model.hasCollisions(): Boolean = carts.any { it.collided }

fun part1(input: Model): Pos {
    val endState = timeline(input).dropWhile { m -> !m.hasCollisions() }.first()
    return endState.cartsInScanOrder.filter { c -> c.collided }.first().pos
}

Part 2

A proper part 2 today, which introduced a new tricky problem. Removing the carts the instant they crash introduces some more complexity to those inter-tick mini-states. We're folding over the carts in scan order, but our fold accumulator is the updated list of carts. These can become out of sync as a collision can happen before the scan order reaches a certain cart, removing it from the simulation. I solved this in a kind-of hacky way by skipping any cart in the fold that has been removed from the list.

fun Model.tick(): Model {
    val newCarts = cartsInScanOrder.fold(carts) { carts_, c ->
        if (!carts_.contains(c)) // removed by collision
            carts_
        else {
            val c_ = c.move(tracks)
            val otherCarts = carts_.filter { it != c }
            val crash = c_.collision(otherCarts)
            if (crash == null)
                otherCarts + c_
            else
                otherCarts.filterNot { it == crash }
        }
    }
    return Model(tracks, newCarts)
}

The part 2 simulation is similar to part 1. Drop states until the end criteria is met, then extract the information required from the next state.

fun part2(input: Model): Pos {
    val endState = timeline(input).dropWhile { m -> m.carts.size > 1 }.first()
    return endState.carts.first().pos
}

[Dane Hillard]

This one seemed like the hardest one so far on first reading, but I ended up grasping it better than a couple of the previous puzzles. I ended up using a deque to make the turning directions easier to muck with:

#!/usr/bin/env python

from collections import deque


class Cart:
    def __init__(self, x, y, current_direction):
        self.x = x
        self.y = y
        self.current_direction = current_direction
        self.num_intersections_reached = 0
        self.directions = deque(['<', 'v', '>', '^'])
        self.collided = False
        while self.directions[0] != self.current_direction:
            self.directions.rotate()

    def move(self):
        self.x += 1 if self.current_direction == '>' else -1 if self.current_direction == '<' else 0
        self.y += 1 if self.current_direction == 'v' else -1 if self.current_direction == '^' else 0

    def turn_left(self):
        self.directions.rotate(-1)
        self.current_direction = self.directions[0]

    def turn_right(self):
        self.directions.rotate(1)
        self.current_direction = self.directions[0]

    def update_direction(self, track):
        track_piece = track[self.y][self.x]

        if track_piece == '+':
            self.num_intersections_reached += 1
            self.num_intersections_reached %= 3

            if self.num_intersections_reached  == 1:
                self.turn_left()
            elif self.num_intersections_reached  == 0:
                self.turn_right()
        elif track_piece == '/':
            if self.current_direction in {'^', 'v'}:
                self.turn_right()
            else:
                self.turn_left()
        elif track_piece == '\\':
            if self.current_direction in {'^', 'v'}:
                self.turn_left()
            else:
                self.turn_right()


def get_next_state(track_state, carts):
    carts.sort(key=lambda cart: (cart.y, cart.x))

    for cart in carts:
        cart.move()
        cart.update_direction(track_state)

        for other_cart in carts:
            if cart != other_cart and cart.x == other_cart.x and cart.y == other_cart.y:
                cart.collided = other_cart.collided = True
                print(f'Crash: {cart.x},{cart.y}')

    carts = [cart for cart in carts if not cart.collided]

    return track_state, carts


def run(track_state, carts):
    while True:
        track_state, carts = get_next_state(track_state, carts)
        if len(carts) == 1:
            print(f'Last cart standing: {carts[0].x},{carts[0].y}')
            return track_state


if __name__ == '__main__':
    with open('input.txt') as track_file:
        track_state = [
            [char for char in line]
            for line in track_file.read().splitlines()
        ]

    carts = []
    for y, row in enumerate(track_state):
        for x, char in enumerate(row):
            if char in {'^', 'v', '>', '<'}:
                carts.append(Cart(x, y, char))

            if char in {'<', '>'}:
                track_state[y][x] = '-'
            elif char in {'^', 'v'}:
                track_state[y][x] = '|'

    track_state = run(track_state, carts)

[Mustafa Haddara]

This is one of those problems that you just gotta grind through, I guess.

Surprisingly, this is the first one where, the first time it compiled, I got the right answer. Of course, getting it to compile took a few tries-- I'm using AoC to learn a new language --but once the syntax issues were ironed out, I just had the solution ready to go.

Only really interesting things are that on the beginning of each tick, I can do

sort!(board.carts, by=c -> (c.y, c.x))

which sorts the array of carts first by y, then by x. Then I can just iterate straight through that array and have the carts in correct order.

I implemented collision checking like so

function check_collisions(carts)
    positions = Set()
    for cart in carts
        pos = (cart.x, cart.y)
        if pos in positions
            return pos
        else
            push!(positions, pos)
        end
    end
    return nothing
end

and sadly have to call it once per cart, per tick. If I only called this at the beginning or end of each tick, then two carts like so:

--><--

would actually end up switching spots, and I'd never notice they overlapped.

For part 2, I replaced my check_collisions method with

function remove_collisions(carts)
    positions = Dict{Tuple{Int, Int}, Array{Cart}}()
    for cart in carts
        pos = (cart.x, cart.y)
        if !haskey(positions, pos)
            positions[pos] = []
        end
        push!(positions[pos], cart)
    end
    carts::Array{Cart} = []
    for c in values(positions)
        if length(c) == 1
            push!(carts, c[1])
        end
    end
    return carts
end

Essentially, instead of merely detecting if there is a collision, this method filters out any carts that have a position that is equal. (Now that I type that out, I realize I could have just called filter()...oh well.)

I'm still calling this once per cart per tick, which is so poorly inefficient that it makes me wince, but there are so few carts in the input that it rarely matters.

Full code here: github.com/MustafaHaddara/advent-o... and github.com/MustafaHaddara/advent-o...

Oh, and last lesson learned: I wrote a print_board() function that didn't actually print the carts! This is really really really stupid...it made that function almost entirely useless.

[E. Choroba]

Perl solution. Most of the decisions are represented by the hash tables at the beginning of the code:

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ first };

use enum qw( X Y FACING TURN );
use enum qw( LEFT STRAIGHT RIGHT );
use constant {
    MOVE => {
        '<' => [ -1,  0 ],
        '>' => [  1,  0 ],
        'v' => [  0,  1 ],
        '^' => [  0, -1 ],
    },
    BEND => {
        '^/'  => '>',
        '^\\' => '<',
        'v/'  => '<',
        'v\\' => '>',
        '</'  => 'v',
        '<\\' => '^',
        '>/'  => '^',
        '>\\' => 'v',
    },
    FACES => [ '^', '>', 'v', '<' ],
};

my (@map, @carts, %crash);
while (<>) {
    chomp;
    while (/([<>^v])/g) {
        push @carts, [ pos() - 1, $. - 1, $1, LEFT ];
        ++$crash{ $carts[-1][X] }{ $carts[-1][Y] };
    }
    s/[<>]/-/g;
    s/[v^]/|/g;
    push @map, [split //, $_, -1];
}

while (1) {
    for my $cart (
        sort { $a->[Y] <=> $b->[Y] || $a->[X] <=> $b->[X] } @carts
    ) {
        --$crash{ $cart->[X] }{ $cart->[Y] };
        my $move = MOVE->{ $cart->[FACING] };
        $cart->[$_] += $move->[$_] for X, Y;
        if ($crash{ $cart->[X] }{ $cart->[Y] }++) {
            say "$cart->[X],$cart->[Y]";
            exit
        }

        my $current = $map[ $cart->[Y] ][ $cart->[X] ];
        next if $current =~ /[-|]/;

        if ('+' eq $current) {
            my $face_index = first { $cart->[FACING] eq FACES->[$_] }
                             0 .. $#{(FACES)};
            $face_index += (-1, 0, 1)[ $cart->[TURN] ];
            $cart->[FACING] = FACES->[ $face_index % 4 ];
            ++$cart->[TURN];
            $cart->[TURN] %= 3;

        } else {
            $cart->[FACING] = BEND->{ $cart->[FACING] . $current };
        }
    }
}

In part 2, I just replaced the code that printed the collision with a new one that removes the two carts involved.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ first };

use enum qw( X Y FACING TURN );
use enum qw( LEFT STRAIGHT RIGHT );
use constant {
    MOVE => {
        '<' => [ -1,  0 ],
        '>' => [  1,  0 ],
        'v' => [  0,  1 ],
        '^' => [  0, -1 ],
    },
    BEND => {
        '^/'  => '>',
        '^\\' => '<',
        'v/'  => '<',
        'v\\' => '>',
        '</'  => 'v',
        '<\\' => '^',
        '>/'  => '^',
        '>\\' => 'v',
    },
    FACES => [ '^', '>', 'v', '<' ],
};

my @map;
my @carts;
my %crash;
while (<>) {
    chomp;
    while (/([<>^v])/g) {
        push @carts, [ pos() - 1, $. - 1, $1, LEFT ];
        ++$crash{ $carts[-1][X] }{ $carts[-1][Y] };
    }
    s/[<>]/-/g;
    s/[v^]/|/g;
    push @map, [split //, $_, -1];
}

while (1) {
    for my $cart (
        sort { $a->[Y] <=> $b->[Y] || $a->[X] <=> $b->[X] } @carts
    ) {
        next unless $cart->[FACING];

        --$crash{ $cart->[X] }{ $cart->[Y] };
        my $move = MOVE->{ $cart->[FACING] };
        $cart->[$_] += $move->[$_] for X, Y;
        if ($crash{ $cart->[X] }{ $cart->[Y] }++) {
            $crash{ $cart->[X] }{ $cart->[Y] } -= 2;
            $cart->[FACING] = 0;
            my $other_cart = first {
                $_->[FACING] && $_->[X] == $cart->[X] && $_->[Y] == $cart->[Y]
            } @carts;
            $other_cart->[FACING] = 0;
            next
        }

        my $current = $map[ $cart->[Y] ][ $cart->[X] ];
        next if $current =~ /[-|]/;

        if ('+' eq $current) {
            my $face_index = first { $cart->[FACING] eq FACES->[$_] }
                             0 .. $#{(FACES)};
            $face_index += (-1, 0, 1)[ $cart->[TURN] ];
            $cart->[FACING] = FACES->[ $face_index % 4 ];
            ++$cart->[TURN];
            $cart->[TURN] %= 3;

        } else {
            $cart->[FACING] = BEND->{ $cart->[FACING] . $current };
        }
    }

    my @left = grep $carts[$_][FACING], 0 .. $#carts;
    next unless 1 == @left;

    say join ',', @{ $carts[ $left[0] ] }[X, Y];
    exit
}

[Tiago Romero]

JavaScript solution

I had to do other things since Wednesday and couldn't focus on AoC until yesterday night but hopefully I will catch up soon!

I created a graph for all the map squares, and a list of carts that move around these squares.

Here's my solutions:

13-common.js

const TURNS = {
    LEFT: Symbol('LEFT'),
    STRAIGHT: Symbol('STRAIGHT'),
    RIGHT: Symbol('RIGHT')
};

const DIRECTIONS = {
    WEST: Symbol('WEST'),
    EAST: Symbol('EAST'),
    NORTH: Symbol('NORTH'),
    SOUTH: Symbol('SOUTH')
};

const MAP = {
    HORIZONTAL: '-',
    VERTICAL: '|',
    INTERSECTION: '+',
    CORNER_NW_SE: '/',
    CORNER_NE_SW: `\\`,
    CART_NORTH: '^',
    CART_EAST: '>',
    CART_SOUTH: 'v',
    CART_WEST: '<'
};

const CART_DIRECTIONS = {
    [MAP.CART_NORTH]: DIRECTIONS.NORTH,
    [MAP.CART_EAST]: DIRECTIONS.EAST,
    [MAP.CART_SOUTH]: DIRECTIONS.SOUTH,
    [MAP.CART_WEST]: DIRECTIONS.WEST
};

const DIRECTIONS_TO_LEFT = {
    [DIRECTIONS.NORTH]: DIRECTIONS.WEST,
    [DIRECTIONS.EAST]: DIRECTIONS.NORTH,
    [DIRECTIONS.SOUTH]: DIRECTIONS.EAST,
    [DIRECTIONS.WEST]: DIRECTIONS.SOUTH,
};

const DIRECTIONS_TO_RIGHT = {
    [DIRECTIONS.NORTH]: DIRECTIONS.EAST,
    [DIRECTIONS.EAST]: DIRECTIONS.SOUTH,
    [DIRECTIONS.SOUTH]: DIRECTIONS.WEST,
    [DIRECTIONS.WEST]: DIRECTIONS.NORTH,
};

class Square {
    constructor({x, y, type}) {
        this.x = x;
        this.y = y;
        this.type = type;
    }

    setCart(cart) {
        if (this.cart) {
            this.cart.crashed = true;
            cart.crashed = true;
        }
        if (cart.square) {
            cart.square.cart = null;
        }
        this.cart = cart;
        this.cart.square = this;
    }
}

let cartId = 0;
class Cart {
    constructor() {
        this.nextTurnIndex = -1;        
        this.id = cartId++;
    }

    getNextTurn() {
        const turns = [TURNS.LEFT, TURNS.STRAIGHT, TURNS.RIGHT];
        this.nextTurnIndex = ++this.nextTurnIndex % turns.length;
        return turns[this.nextTurnIndex];
    }

    moveHorizontal() {
        if (this.direction === DIRECTIONS.EAST) {
            this.square.right.setCart(this);
        }
        else if (this.direction === DIRECTIONS.WEST) {
            this.square.left.setCart(this);
        }
    }

    moveVertical() {
        if (this.direction === DIRECTIONS.SOUTH) {
            this.square.bottom.setCart(this);
        }
        else if (this.direction === DIRECTIONS.NORTH) {
            this.square.top.setCart(this);
        }
    }

    move() {
        if (this.square.type === MAP.HORIZONTAL) {
            this.moveHorizontal();
        }
        else if (this.square.type === MAP.VERTICAL) {
            this.moveVertical();
        }
        else if (this.square.type === MAP.INTERSECTION) {
            const turn = this.getNextTurn();
            if (turn === TURNS.LEFT) {
                this.direction = DIRECTIONS_TO_LEFT[this.direction];
            }
            else if (turn === TURNS.RIGHT) {
                this.direction = DIRECTIONS_TO_RIGHT[this.direction];
            }
            this.moveHorizontal();
            this.moveVertical();
        }
        else if (this.square.type === MAP.CORNER_NW_SE) {
            if ([DIRECTIONS.NORTH, DIRECTIONS.SOUTH].includes(this.direction)) {
                this.direction = DIRECTIONS_TO_RIGHT[this.direction];
                this.moveHorizontal();
            }
            else if ([DIRECTIONS.WEST, DIRECTIONS.EAST].includes(this.direction)) {
                this.direction = DIRECTIONS_TO_LEFT[this.direction];
                this.moveVertical();
            }
        }
        else if (this.square.type === MAP.CORNER_NE_SW) {
            if ([DIRECTIONS.NORTH, DIRECTIONS.SOUTH].includes(this.direction)) { 
                this.direction = DIRECTIONS_TO_LEFT[this.direction];
            }
            else if ([DIRECTIONS.WEST, DIRECTIONS.EAST].includes(this.direction)) {
                this.direction = DIRECTIONS_TO_RIGHT[this.direction];                
            }
            if ([DIRECTIONS.WEST, DIRECTIONS.EAST].includes(this.direction)) {
                this.moveHorizontal();
            }
            else if ([DIRECTIONS.NORTH, DIRECTIONS.SOUTH].includes(this.direction)) { 
                this.moveVertical();
            }
        }
    }
}

const buildMap = lines => lines.map(line => line.split(''));

const getSquareType = col => {
    let type;
    if ([MAP.CART_NORTH, MAP.CART_SOUTH].includes(col)) {
        type = MAP.VERTICAL;
    }
    else if ([MAP.CART_EAST, MAP.CART_WEST].includes(col)) {
        type = MAP.HORIZONTAL;
    } 
    else {
        type = col;
    }
    return type;
}

const getCartDirection = col => CART_DIRECTIONS[col];

const buildPath = map => {
    const carts = [];
    const squares = new Map();

    const n = map.length;
    for (let i = 0; i < n; i++) {
        const row = map[i];
        const m = row.length;
        for (let j = 0; j < m; j++) {
            const col = map[i][j];
            if (Object.values(MAP).includes(col)) {
                const square = new Square({
                    x: i, 
                    y: j,
                    type: getSquareType(col)
                });
                squares.set(`${i},${j}`, square);

                if ([MAP.CART_NORTH, MAP.CART_EAST, MAP.CART_SOUTH, MAP.CART_WEST].includes(col)) {
                    const cart = new Cart();
                    square.setCart(cart);

                    cart.direction = getCartDirection(col);
                    carts.push(cart);
                }

                const previousHorizontal = squares.get(`${i},${j-1}`);
                const previousVertical = squares.get(`${i-1},${j}`);
                if (square.type === MAP.HORIZONTAL) {
                    previousHorizontal.right = square;
                    square.left = previousHorizontal;
                }
                else if (square.type === MAP.VERTICAL) {
                    previousVertical.bottom = square;
                    square.top = previousVertical;
                }
                else if (square.type === MAP.INTERSECTION) {                    
                    previousHorizontal.right = square;
                    square.left = previousHorizontal;

                    previousVertical.bottom = square;
                    square.top = previousVertical;
                }
                else if (square.type === MAP.CORNER_NW_SE) {
                    if (previousHorizontal && 
                        [MAP.HORIZONTAL, MAP.INTERSECTION, MAP.CORNER_NE_SW].includes(previousHorizontal.type) &&
                        previousVertical && 
                        [MAP.VERTICAL, MAP.INTERSECTION, MAP.CORNER_NE_SW].includes(previousVertical.type)) { // SE
                        previousHorizontal.right = square;
                        square.left = previousHorizontal;

                        previousVertical.bottom = square;
                        square.top = previousVertical;
                    }
                }
                else if (square.type === MAP.CORNER_NE_SW) {
                    if (previousHorizontal && 
                        [MAP.HORIZONTAL, MAP.INTERSECTION, MAP.CORNER_NW_SE].includes(previousHorizontal.type)) { // NE
                        previousHorizontal.right = square;
                        square.left = previousHorizontal;
                    }
                    else if (previousVertical && 
                        [MAP.VERTICAL, MAP.INTERSECTION, MAP.CORNER_NW_SE].includes(previousVertical.type)) { // SW
                        previousVertical.bottom = square;
                        square.top = previousVertical;
                    }
                }
            }
        }
    }

    return { squares, carts };
};

module.exports = {
    buildMap,
    buildPath
};

13a.js

const { readFile } = require('./reader');
const {
    buildMap,
    buildPath
} = require('./13-common');

const getSquareCrash = carts => {
    while (true) {
        carts.sort((a, b) => {
            const sA = a.square;
            const sB = b.square;
            return (sA.x === sB.x) ? sA.y - sB.y : sA.x - sB.x;
        });
        for (let cart of carts) {
            cart.move();
            if (cart.crashed) {
                return cart.square;
            }
        }
    };
};

(async () => {
    const lines = await readFile('13-input.txt');
    const map = buildMap(lines);
    const { squares, carts } = buildPath(map);
    const square = getSquareCrash(carts);

    console.log(`The location of the first crash is ${square.y},${square.x}`);
})();

13b.js

const { readFile } = require('./reader');
const {
    buildMap,
    buildPath
} = require('./13-common');

const getRemainingCart = carts => {
    let tick = 0;
    while (carts.length > 1) {
        carts.sort((a, b) => {
            const sA = a.square;
            const sB = b.square;
            return (sA.x === sB.x) ? sA.y - sB.y : sA.x - sB.x;
        });
        for (let cart of carts) {
            if (!cart.crashed) {
                cart.move();
                if (cart.crashed) {
                    cart.square.cart = null;
                }
            }
        }
        carts = carts.filter(cart => !cart.crashed);
        tick++
    };

    return carts[0];
};

(async () => {
    const lines = await readFile('13-input.txt');
    const map = buildMap(lines);
    const { squares, carts } = buildPath(map);
    const cart = getRemainingCart(carts);

    console.log(`The location of the last cart ${cart.id} is ${cart.square.y},${cart.square.x}`);
})();

[Ryan Palo]

Alright, now I'm making up ground on the ones I got behind on. I actually really enjoyed this one! It was fun tuning things to be readable and easy to follow.

"""Day 13: Mine Cart Madness

Figure out when carts on tracks will crash
"""

from typing import List


class Vector:
    """A 2D vector.  Right is +X, Down is +Y"""

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __repr__(self):
        return f"Vector({self.x}, {self.y})"

    def __str__(self):
        return f"<{self.x}, {self.y}>"

    def __hash__(self):
        return hash((self.x, self.y))


NORTH = Vector(0, -1)
SOUTH = Vector(0, 1)
EAST = Vector(1, 0)
WEST = Vector(-1, 0)
DIRECTIONS = [NORTH, EAST, SOUTH, WEST]


class Cart:
    """A cart that drives around the mine"""

    def __init__(self, position: Vector, direction: Vector):
        self.position = position
        self.direction = direction
        self.next_turn = "left"

    def move(self):
        """Updates position based on direction"""
        self.position += self.direction

    def turn_right(self):
        self.direction = DIRECTIONS[
            (DIRECTIONS.index(self.direction) + 1) % len(DIRECTIONS)
        ]

    def turn_left(self):
        self.direction = DIRECTIONS[
            (DIRECTIONS.index(self.direction) - 1) % len(DIRECTIONS)
        ]

    def handle_next_turn(self):
        """Update own direction based on the next turn value specified in the prompt"""
        if self.next_turn == "left":
            self.turn_left()
            self.next_turn = "straight"
        elif self.next_turn == "straight":
            self.next_turn = "right"
        elif self.next_turn == "right":
            self.turn_right()
            self.next_turn = "left"


class Mine:
    """A mine that has a bunch of different carts on tracks"""

    def __init__(self, map: str):
        self.map = []
        self.carts: List[Cart] = []
        for y, line in enumerate(map.splitlines()):
            self.map.append([])
            for x, c in enumerate(line):
                if c == '>':
                    self.carts.append(Cart(Vector(x, y), EAST))
                    self.map[-1].append('-')
                elif c == '<':
                    self.carts.append(Cart(Vector(x, y), WEST))
                    self.map[-1].append('-')
                elif c == '^':
                    self.carts.append(Cart(Vector(x, y), NORTH))
                    self.map[-1].append('|')
                elif c == 'v':
                    self.carts.append(Cart(Vector(x, y), SOUTH))
                    self.map[-1].append('|')
                else:
                    self.map[-1].append(c)

    def find_first_collision(self) -> Vector:
        """Simulates the mine until two carts collide.  Returns that x, y pair"""
        while True:
            self.sort_carts()

            for cart in self.carts:
                cart.move()
                self.turn_cart(cart)

                if self.is_collision(cart):
                    return cart.position

    def last_cart_location(self) -> Vector:
        """Simulates the mine, removing carts when they collide.
        Returns the x, y pair of the last cart standing
        """
        while True:
            self.sort_carts()

            crashed = set()
            for cart in self.carts:
                if cart.position in crashed:
                    continue
                cart.move()
                self.turn_cart(cart)

                if self.is_collision(cart):
                    crashed.add(cart.position)
                    continue

            self.carts = [cart
                          for cart in self.carts
                          if cart.position not in crashed]
            if len(self.carts) == 1:
                return self.carts[0].position

    def sort_carts(self):
        """Carts are always run in reading order, top to bottom, left to right"""
        self.carts.sort(key=lambda cart: (cart.position.y, cart.position.x))

    def is_collision(self, cart: Cart) -> bool:
        """Checks whether or not a cart is running into any other carts"""
        return sum(other.position == cart.position for other in self.carts) > 1

    def turn_cart(self, cart: Cart):
        """Depending on what kind of track the cart is on, turn it appropriately"""
        track_type = self.map[cart.position.y][cart.position.x]
        if track_type == '+':
            cart.handle_next_turn()
        elif track_type == '/':
            if cart.direction == NORTH or cart.direction == SOUTH:
                cart.turn_right()
            else:
                cart.turn_left()
        elif track_type == '\\':
            if cart.direction == NORTH or cart.direction == SOUTH:
                cart.turn_left()
            else:
                cart.turn_right()


if __name__ == "__main__":
    with open("python/data/day13.txt", "r") as f:
        mine_map = f.read()

    # Part 1
    mine = Mine(mine_map)
    print(mine.find_first_collision())

    # Part 2
    mine = Mine(mine_map)
    print(mine.last_cart_location())