## DEV Community Ryan Palo

Posted on

# 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! 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)
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.x, carts.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:
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! 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. Ali Spittel • Edited

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:
carts = [cart for cart in carts if cart.coordinates() in seen]
return carts

def get_collision(carts):
seen = set()
for cart in carts:
cart.move()
if (cart.x, cart.y,) in seen:
return cart
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). 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')
.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) {
car.moves = backDirChange[`moves\${car.moves}`];
} else if (data[car.row] && data[car.row][car.position] === curves) {
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 };
}

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'
});
}
});
});
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) {
}
let remaining = howManyCartsLeft(carPositions);
if (remaining.number === 1) {
i = Infinity;
}
});
}
return {
};
}

})();
`````` 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>)
``````

The input text lines are just mapped to `CharArray`s. 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 {
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
}
`````` 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)
positions[pos] = []
end
push!(positions[pos], cart)
end
carts::Array{Cart} = []
for c in values(positions)
if length(c) == 1
push!(carts, c)
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.

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. Tiago Romero Garcia • Edited

## 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 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;
};

(async () => {
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}`);
})();
`````` Dane Hillard • Edited

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 != 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

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

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.x},{carts.y}')
return track_state

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

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)
`````` 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

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;
}

[\$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";
?>
``````

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

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

fclose(\$file);

return array_filter(\$array);
?>
`````` 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 ] }[X, Y];
exit
}
`````` 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

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):
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):
continue

self.carts = [cart
for cart in self.carts
if cart.position not in crashed]
if len(self.carts) == 1:
return self.carts.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:

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

# Part 2
mine = Mine(mine_map)
print(mine.last_cart_location())
`````` Jon Bristow • Edited

Oof, I played with this too long.

Here's it all.

### Kotlin Solution

``````private fun answer1(input: List<String>) =
step(0, input.findCarts(), input)

demolitionStep(0, input.findCarts(), input)

tailrec fun step(
i: Int,
carts: List<Cart>,
tracks: List<String>
): Point {
val (nextCarts, collisions) =
moveCarts(carts = carts.sorted(), tracks = tracks)

return when {
collisions.isEmpty() -> step(i + 1, nextCarts, tracks)
else -> collisions.first().loc
}
}

tailrec fun moveCarts(
carts: List<Cart>,
moved: List<Cart> = emptyList(),
collided: List<Cart> = emptyList(),
tracks: List<String>
): Pair<List<Cart>, List<Cart>> {

if (carts.isEmpty()) return moved to collided

val (ucRem, cRem) = carts.tail.splitBy { it.loc == h.loc }
val (ucMoved, cMoved) = moved.splitBy { it.loc == h.loc }

return when {
cRem.isEmpty() && cMoved.isEmpty() ->
moveCarts(ucRem, ucMoved + h, collided, tracks)
cRem.isEmpty() ->
moveCarts(ucRem, ucMoved, collided + h + cMoved, tracks)
cMoved.isEmpty() ->
moveCarts(ucRem, ucMoved, collided + h + cRem, tracks)
else ->
moveCarts(ucRem, ucMoved, collided + h + cRem + cMoved, tracks)
}

}

tailrec fun demolitionStep(
i: Int,
carts: List<Cart>,
tracks: List<String>
): Point {
val (nextCarts, collisions) = moveCarts(
carts = carts.sorted(),
tracks = tracks
)
return when {
carts.count() == 1 -> carts.first().loc
else -> demolitionStep(i + 1, nextCarts, tracks)
}
}

enum class Choice {
LEFT {
override fun makeChoice(cart: Cart) = when (cart.direction) {
Direction.RIGHT -> cart.nextPosition(Direction.UP, Choice.LEFT)
Direction.LEFT -> cart.nextPosition(Direction.DOWN, Choice.LEFT)
Direction.UP -> cart.nextPosition(Direction.LEFT, Choice.LEFT)
Direction.DOWN -> cart.nextPosition(Direction.RIGHT, Choice.LEFT)
}
},
RIGHT {
override fun makeChoice(cart: Cart) = when (cart.direction) {
Direction.LEFT -> cart.nextPosition(Direction.UP, Choice.RIGHT)
Direction.RIGHT -> cart.nextPosition(Direction.DOWN, Choice.RIGHT)
Direction.UP -> cart.nextPosition(Direction.RIGHT, Choice.RIGHT)
Direction.DOWN -> cart.nextPosition(Direction.LEFT, Choice.RIGHT)
}
},
STRAIGHT {
override fun makeChoice(cart: Cart) =
when (cart.direction) {
Direction.RIGHT, Direction.LEFT ->
cart.nextPosition(cart.direction, Choice.STRAIGHT)
Direction.DOWN, Direction.UP ->
cart.nextPosition(cart.direction, Choice.STRAIGHT)
}
};

abstract fun makeChoice(cart: Cart): Cart
}

enum class Direction(val char: Char) {
UP('^') {
override fun turnBack() = LEFT
override fun turnForward() = RIGHT
override fun move(loc: Point) = Point(loc.x, loc.y - 1)
},
DOWN('v') {
override fun turnBack() = RIGHT
override fun turnForward() = LEFT
override fun move(loc: Point) = Point(loc.x, loc.y + 1)
},
LEFT('<') {
override fun turnBack() = UP
override fun turnForward() = DOWN
override fun move(loc: Point) = Point(loc.x - 1, loc.y)
},
RIGHT('>') {
override fun turnBack() = DOWN
override fun turnForward() = UP
override fun move(loc: Point) = Point(loc.x + 1, loc.y)
};

abstract fun move(loc: Point): Point
abstract fun turnBack(): Direction
abstract fun turnForward(): Direction

override fun toString(): String = this.char.toString()
}

fun Char.toDirection(): Direction? {
return Direction.values().find { it.char == this }
}

fun <E> Direction?.whenNotNull(function: (Direction) -> E): E? = when {
this != null -> function(this)
else -> null
}

class OffTheRailsException(cart: Point) : Exception("Off the rails! \$cart")

data class Cart(
val loc: Point,
val direction: Direction,
val lastChoice: Choice?,
val id: Int
) : Comparable<Cart> {
override fun compareTo(other: Cart) =
when (val ycomp = y.compareTo(other.y)) {
0 -> x.compareTo(other.x)
else -> ycomp
}

constructor(loc: Point, direction: Direction, lastChoice: Choice?) : this(
loc,
direction,
lastChoice,
loc.hashCode() + direction.hashCode()
)

}

fun Cart.nextPosition(direction: Direction, lastChoice: Choice?) =
Cart(direction.move(loc), direction, lastChoice, id)

fun Cart.nextPosition(direction: Direction) =
Cart(direction.move(loc), direction, lastChoice, id)

// '\'
fun Cart.turnBackCorner() = nextPosition(direction.turnBack())

// '/'
fun Cart.turnForwardCorner() = nextPosition(direction.turnForward())

val Cart.x: Int get() = loc.x
val Cart.y: Int get() = loc.y

fun Cart.move(tracks: List<String>) = when (tracks[y][x]) {
'|', '^', 'v' -> nextPosition(
direction
)
'-', '<', '>' -> nextPosition(
direction
)
'\\' -> turnBackCorner()
'/' -> turnForwardCorner()
'+' -> intersection()
else -> throw OffTheRailsException(loc)
}

fun Cart.intersection() = when (lastChoice) {
null, Choice.RIGHT -> Choice.LEFT.makeChoice(this)
Choice.STRAIGHT -> Choice.RIGHT.makeChoice(this)
Choice.LEFT -> Choice.STRAIGHT.makeChoice(this)
}

fun <E> List<E>.splitBy(predicate: (E) -> Boolean) =
groupBy(predicate).let {
(it[false] ?: emptyList()) to (it[true] ?: emptyList())
}

fun List<String>.findCarts() =
mapIndexed { y, xl ->
xl.mapIndexedNotNull { x, c ->
c.toDirection().whenNotNull {
Cart(Point(x, y), it, null)
}
}
}.flatten()
``````