Advent of Code 2018 Day 13 - Detect mine cart collisions

Question

This is a solution to Advent of Code Day 13 (problem specification, test input), for which I was asked to read a layout of tracks and mine carts and detect 1) where the first crash would occur and 2) where the final remaining cart would be after the rest had crashed.

The tracks consist of:
spaces: there's nothing there
straight pieces: -s and |s
Curves: \s, which connect top/right and bottom/left, and /s which do the opposite
Intersections: +s, for which carts alternate between going left/straight/right
Carts: v, ^, <, > start on straight tracks facing the direction of the arrow

Carts move in an order determined by their position. Lower y-values move first, lower-x values break ties, they move one unit along their track per tick, and when carts crash they both disappear.

My code consists of the main function day13 and a Cart class. The Cart class stores the track layout. Each cart keeps track of its position, direction, and which turn it will take next. It exposes its position and a move function.

The main function reads the input to initialize the track layout and puts all the carts in a map using keys sorted by move-order. And the main loop moves each cart, checks for collisions, and continues until there's only one cart left.

Without further ado, the Cart.h/Cart.cpp code:

#pragma once
#include<array>
using std::array;
#include<utility>
using std::pair;

constexpr auto infile = "Day13Input.txt";
constexpr auto track_size = 150;

namespace Day13 {
    enum Track {
        None = 0,
        Vert = 1,
        Flat = 2,
        Cross = 3,
        Hack = 4,
        Slash = 5,
    };

    enum Dir {
        Up = 0,
        Right = 1,
        Down = 2,
        Left = 3,
    };

    enum Turn {
        LeftTurn = -1,
        Straight = 0,
        RightTurn = 1,
    };

    class Cart {
    private:
        Dir _dir;
        Turn _turn_dir;

        void derail ( ) const;
        void turn ( const Track t );
        pair<int, int> dest ( ) const;
        Track lookup_dest ( const pair<int, int> ) const;

    public:
        static array<array<Track, track_size>, track_size> tracks;
        int _x, _y;
        Cart ( int x, int y, Dir dir ) : _x ( x ), _y ( y ), _dir ( dir ), _turn_dir ( Turn::LeftTurn ) { };

        int move ( );

        bool operator<( const Cart& rhs ) const;
        bool operator==( const Cart& rhs ) const;
        bool operator>( const Cart& rhs ) const;
    };
}

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include "Day13CartClass.h"
using Day13::Turn;
using Day13::Dir;
using Day13::Track;
using Day13::Cart;
#include<utility>
using std::pair;
#include<exception>
using std::exception;
#include<array>
using std::array;

//not sure if this is obvious enough behavior for overloaded ++
Turn operator++( Turn& orig ) {
    orig = (Turn) ( orig == 1 ? -1 : orig + 1 );
    return orig;
}

Turn operator++( Turn& orig, int ) {
    Turn ret = orig;
    ++orig;
    return ret;
}

Dir make_turn ( const Dir initial_dir, const Turn turn_type ) {
    return (Dir) ( ( initial_dir + turn_type + 4 ) % 4 );
}

Dir follow_curve ( const Dir initial_dir, const Track curve ) {
    Dir new_dir;
    switch ( curve ) {
        case Track::Hack:
            new_dir = (Dir) ( 3 - initial_dir );
            break;
        case Track::Slash:
            new_dir = (Dir) ( initial_dir ^ 1 );
            break;
        default:
            throw exception ( "tried to follow a curve that wasn't curved\n" );
    }

    return new_dir;
}

array<array<Track, track_size>, track_size> Cart::tracks;

pair<int, int> Cart::dest ( ) const {
    int new_x = _x, new_y = _y;
    switch ( _dir ) {
        case Up:
            new_y--;
            break;
        case Down:
            new_y++;
            break;
        case Left:
            new_x--;
            break;
        case Right:
            new_x++;
            break;
    }
    return std::pair<int, int> ( new_x, new_y );
}

void Cart::turn ( const Track t ) {
    switch ( t ) {
        case Vert:
            if ( _dir == Right || _dir == Left )
                derail ( );
            break;
        case Flat:
            if ( _dir == Up || _dir == Down )
                derail ( );
            break;
        case Hack:
        case Slash:
            _dir = follow_curve ( _dir, t );
            break;
        case Cross:
            _dir = make_turn ( _dir, _turn_dir++ );
            break;
        case None:
            derail ( );
            break;
    }
}

void Cart::derail ( ) const {
    char* buf = new char[ 100 ];
    sprintf ( buf, "Cart went off the rails at %d, %d with direction %d", _x, _y, _dir );
    throw exception ( buf );
}

Track Cart::lookup_dest ( const pair<int, int> coords ) const {
    return tracks[ coords.second ][ coords.first ];
}

int Cart::move ( ) {
    auto dest = this->dest ( );
    Track t = lookup_dest ( dest );

    _x = dest.first; _y = dest.second;
    this->turn ( t );

    return ( _y * track_size ) + _x;
}

bool Cart::operator<( const Cart& rhs ) const {
    if ( _y < rhs._y )
        return true;
    else if ( _y == rhs._y )
        return _x < rhs._x;
    else
        return false;
}

bool Cart::operator==( const Cart& rhs ) const {
    return ( _x == rhs._x ) && ( _y == rhs._y );
}

bool Cart::operator>( const Cart& rhs ) const {
    return rhs < *this;
}

and the main function is:

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include "Day13CartClass.h"
using Day13::Cart;
using Day13::Track;
using Day13::Dir;

#include<cstdio>
#include<array>
using std::array;

#include<map>
using std::map;

void read_tracks ( FILE*,
                   array<array<Track, track_size>, track_size>&,
                   map<int, Cart*>& );
bool log_crash ( const int );

void day13 ( ) {
    map<int, Cart*> carts = { };

    FILE* input = fopen ( infile, "r" );
    if ( input == nullptr ) {
        printf ( "failed to open input file\n" );
        return;
    }

    read_tracks ( input, Cart::tracks, carts );

    bool crashed = false;
    while ( carts.size ( ) > 1 ) {
        map<int, Cart*> new_carts = { };
        for ( auto it = carts.begin ( ); it != carts.end ( ); ) {
            Cart* cart = it->second;
            int pos = cart->move ( );

            //If the new position is on an existing cart, erase it and don't save this cart, otherwise save new position
            if ( carts.count ( pos ) ) {
                //Check carts that haven't moved
                carts.erase ( pos );
                crashed = crashed || log_crash ( pos );
            } else if ( new_carts.count ( pos ) ) {
                //Check against carts that have already moved
                new_carts.erase ( pos );
                crashed = crashed || log_crash ( pos );
            } else {
                new_carts[ pos ] = cart;
            }
            //erase now that the cart has moved
            it = carts.erase ( it );
        }
        carts = new_carts;
    }

    int x = ( carts.begin ( )->first ) % track_size;
    int y = ( carts.begin ( )->first ) / track_size;
    printf ( "last remaining cart at x=%d and y=%d\n", x, y );
}

//Some rather verbose IO follows
void read_tracks ( FILE* input,
                   array<array<Track, track_size>, track_size>& tracks,
                   map<int, Cart*>& carts ) {
    for ( int y = 0; y < track_size; y++ ) {
        for ( int x = 0; x < track_size; x++ ) {
            char t;
            int pos = ( ( track_size * y ) + x );

            if ( fscanf ( input, "%c", &t ) != 1 ) {
                printf ( "expected character but no match\n" );
                return;
            }

            switch ( t ) {
                case '<':
                    carts[ pos ] = new Cart ( x, y, Dir::Left );
                    t = '-';
                    break;
                case '>':
                    carts[ pos ] = new Cart ( x, y, Dir::Right );
                    t = '-';
                    break;
                case '^':
                    carts[ pos ] = new Cart ( x, y, Dir::Up );
                    t = '|';
                    break;
                case 'v':
                    carts[ pos ] = new Cart ( x, y, Dir::Down );
                    t = '|';
                    break;
            }

            switch ( t ) {
                case '-':
                    tracks[ y ][ x ] = Track::Flat;
                    break;
                case '|':
                    tracks[ y ][ x ] = Track::Vert;
                    break;
                case '\\':
                    tracks[ y ][ x ] = Track::Hack;
                    break;
                case '/':
                    tracks[ y ][ x ] = Track::Slash;
                    break;
                case '+':
                    tracks[ y ][ x ] = Track::Cross;
                    break;
                default:
                    printf ( "weird input found\n" );
                case ' ':
                    tracks[ y ][ x ] = Track::None;
            }
        }

        char eol;
        if ( fscanf ( input, "%c", &eol ) == EOF ) {
            printf ( "unexpected EOF\n" );
            return;
        } else if ( eol != '\n' ) {
            printf ( "expected newline not found\n" );
            return;
        }
    }
}

bool log_crash ( const int pos ) {
    int first_crash_x = pos % track_size;
    int first_crash_y = pos / track_size;
    printf ( "first crash at x=%d and y=%d\n", first_crash_x, first_crash_y );
    return true;
}

The problem input I got (requires a newline at the end if you want it to run):

                      /------------\           /----------------\      /---------------------\                                                        
                      |            |           |    /----------\|      |       /-------------+--------------------------------------------------\     
                      |            |     /-----+----+----------++------+-------+-------------+-----------------------------------\              |     
                      |            |     |     |    |          ||      |       |             |                         /---------+--------------+-\   
                      |            |     |     |    |          ||      |  /----+-------------+-------------------------+---------+----\         | |   
                     /+------------+-----+-----+----+----------++------+--+----+-------------+-------------------------+--------\|    |/--------+-+\  
                     ||   /--------+-\  /+-----+----+----------++------+--+----+-------------+-----\                   |        ||    ||        | ||  
                     ||   | /------+-+--++--\  |    |          ||      |  |    |       /-<---+-----+-------------------+--------++\   ||        | ||  
      /--------------++---+-+------+-+--++--+--+----+----------++------+--+----+-------+-----+-----+--------------\    |        |||   ||        | ||  
      |              ||   | |      | |  ||  |  |    |          ||  /---+--+----+-------+-----+-----+------------\ |    |        |||   ||        | ||  
      |         /----++---+-+------+-+--++--+--+----+----------++-\|   |  |    |       |     |     |            | |    |        |||   ||        | ||  
   /--+---------+----++---+-+------+-+--++--+--+----+----------++-++---+--+----+-\     |     |     |            | |    |        |||   ||        | ||  
   |  |         |    ||   | |      | |  ||  |  |    |        /-++-++---+--+----+-+-----+-----+-----+------------+-+----+--------+++---++-\      | ||  
   |  |         |    ||   | |      | |  ||  | /+----+---\    | || ||   |  |    | |     |     |     |            | |    |  /-----+++---++\|      | ||  
   |  |         |    ||   | |      | |  ||  | ||    \---+----+-/|/++---+--+----+-+-----+---\ |     |/-----------+-+----+\ |     |||   ||||      | ||  
   |  |         |    ||   | |      | |  ||/-+-++--------+----+--++++---+--+>---+-+-----+---+-+-----++-----------+-+----++-+-----+++---++++----\ | ||  
   |  |         |    ||   | |      | |  ||| | ||        |    |  ||||   |  |    | |     | /-+-+-----++-------\   | |    || |     |||   ||||    | | ||  
   |  |         |  /-++---+-+------+-+--+++-+-++<-------+----+--++++---+--+----+-+-----+-+-+-+-----++\      |   | |    || |     |||   ||||    | | ||  
   |  |        /+--+-++---+-+--\   | |  ||| | ||        |    |  ||||   |  |    | |     | | | | /---+++------+---+-+----++-+-----+++---++++----+-+-++-\
   |  |        ||  | ||   | |  |   | | /+++-+-++--------+----+--++++---+--+----+-+--\  | | | | |   v||      |   | |    || |     |||   ||||    | | || |
   |  |        ||/-+-++---+-+--+---+-+-++++-+-++-\ /----+----+\ ||||   |  |    | |  |  | | | | |   |||      |   | |    || |     |||   ||||    | | || |
   |  |        |\+-+-++---+-+--+---+-+-++++-+-++-+-+----+----++-++/|   |  |    | |  |  | | | | |   |||      |   | |    || |     |||   ||||    | | || |
   |  |        | | | ||   | |  |   | | |||| | || | |    |    || || |   |  |    | |  |  | | | | |   |||      |   | |    || |     |||   ||||    | | || |
  /+--+--------+-+-+-++---+-+--+---+-+-++++-+-++-+-+----+\   || || |   \--+----+-+--+--+-+-+-/ |   |||      |   | |    || |     |||   ||||    | | || |
  ||  \--------+-+-+-++---+-+--+---+-+-++++-+-++-+-+----++---++-++-+------+----+-+--+--+-+-+---+---+++------+---+-/    || |     |||   ||||    | | || |
  ||           | | | ||   | |  | /-+-+-++++-+-++-+-+----++---++-++-+------+--\ | |  |  | | |   |   |||      |   |      || |     |||   ||||    | | || |
  ||      /----+-+-+-++---+-+--+-+-+-+-++++-+-++-+-+----++---++-++-+----\ |  | | |  |  | | |   |   |||      |   |      || |     |||   ||||    | | || |
  ||      |    | | | ||   | \--+-+-+-+-++++-/ || | |    ||   || || |    | |  | | |  |  | | |   |   |||      |   |      || |     |||   ||||    | | || |
  ||      |    | | | ||   |    | | | | ||||   || | |    ||   || || |    | |  | | |  |  | | |   |   |||      |   |      || |     |||   ||||    | | || |
  ||   /--+----+-+-+-++---+-\  | | | | ||||   || | |    ||   || || |    | |  | | |  |  | | |   |   |||      |   |      || |     |||   ||||    | | || |
  || /-+--+----+-+-+-++---+-+--+-+-+-+-++++---++-+-+\   ||   || || |  /-+-+--+-+-+--+--+-+\|   |   |||      |   |      || |     |||   ||||    | | || |
  || | |  |    | \-+-++---+-+--+-+-+-+-++++---++-/ ||   ||/--++-++-+-\| | |  | | |  |  | |||   |  /+++------+---+\     || |     |||   ||||    | | || |
  || | |  |    |   | ||   | |  | | | | ||||   ||   \+---+++--+/ || | || | |  | | |  |  | |||   |  ||||      |   ||     || |     |||   ||||    | | || |
  || | |  |    |   | ||  /+-+--+-+-+-+-++++---++----+---+++--+--++-+-++-+-+--+-+\|/-+--+-+++---+--++++------+---++-----++-+-----+++--\||||    | | || |
  || | |  |    |   | ||  || |  | | | | ||\+---++----+---+++--+--++-+-++-+-+--+-++++-+--+-+++---+--++++------+---++-----++-+-----+/|  |||||    | | || |
  || | |  |    |  /+-++--++-+--+-+-+-+-++-+---++----+---+++--+--++-+-++-+-+--+-++++-+--+-+++---+--++++----\ |   ||     || |     | |  |||||    | | || |
  || | |  |    |  || ||  || |  | | | | || |   ||/---+---+++--+--++-+-++-+-+--+-++++-+--+-+++---+--++++----+-+---++-----++-+----\| |  |||||/---+-+-++\|
  || | |  |    |  || ||  || |  | | | | |\-+---+++---+---+++--+--++-+-++-+-+--+-++++-+--+-+++---+--+/||    | |   ||  /--++-+----++-+--++++++---+-+\||||
/-++-+-+--+----+--++-++--++-+--+-+-+-+\|  |   |||/--+---+++--+-\|| | || | |  | |||| |  | |||   |  | ||    | |   ||  |  || |    || |  ||||||   | ||||||
| || | |  |    |  || ||  || |/-+-+-+-+++--+---++++\ |   |||  \-+++-+-++-+-+--+-++++-+--+-+++---+--+-++----+-+---++--+--++-+----++-+--++++/|   | ||||||
| || | |  |    |  || ||  || || | | | |||/-+---+++++-+---+++----+++-+-++-+-+--+-++++-+--+-+++---+--+-++----+-+-\ ||  |  || |    || |  ||\+-+---+-+++/||
| || | |  |    |  || ||  || || | | | |||| |   ||||| |/--+++----+++-+-++-+-+--+-++++-+--+-+++---+--+-++----+-+-+-++--+--++-+----++\|  || | |   | ||| ||
| || | |  |    |  || ||  || || | | | |||| | /-+++++-++--+++----+++-+-++-+-+--+-++++-+--+-+++---+--+-++----+-+-+-++--+-\|| |    ||||  || | |   | ||| ||
| || | |  |    |  || ||  || || | | | |||| | | ||||| ||  |||    ||| | || | |  | |||| |  | |||   |  \-++----+-+-+-+/  | ||| |    ||||  || | |   | ||| ||
| || |/+--+----+--++-++--++-++-+-+-+-++++-+-+-+++++-++--+++----+++-+-++-+-+--+-++++-+--+\|||   |    ||    | | | |   | ||| |    ||||  || | |   | ||| ||
| || |||  |    |  || ||  || || | | | |||| | | ||||| ||  |||    ||| | || | |  | |||| |  \++++---+----++----+-+-+-+---+-+++-+-->-+++/  || | |   | ||| ||
| || |||  |    |  || ||  || || |/+-+-++++-+-+-+++++-++--+++----+++-+-++-+-+-\| ||^| |   ||||   |    ||    | | | |   | ||| |    |||   || | |   | ||| ||
| || |||  |    |  || ||/-++-++-+++-+-++++-+-+-+++++-++--+++----+++-+-++-+-+-++-++++-+---++++---+----++----+-+-+-+---+-+++-+-\  |||   || | |   | ||| ||
| ||/+++--+----+-\|| |||/++-++-+++-+-++++-+-+-+++++-++--+++----+++\| || | | || |||| |   ||||   |    ||    | | | |   | ||| | |  |||   || | |   | ||| ||
| ||||||  |    | ||| |||||| ||/+++-+-++++-+-+-+++++-++--+++----+++++-++-+-+-++-++++-+---++++---+----++\   | | | |   | |\+-+-+--+++---++-+-+---+-++/ ||
| ||||||  |    | ||| |||||| |||||| | |||| | | ||||| ||  |||    ||||| || | | || |||| |   ||||   |    |||   | | | |   | | | | |  |||   || | |   | ||  ||
| ||||||  |    | ||| |||||| |||||\-+-++++-+-+-+++++-++--+++----+++++-++-+-+-+/ |||| | /-++++---+----+++---+-+-+-+---+-+-+-+-+--+++-\ || | |   | ||  ||
| ||||||  |    | ||| |||||| |||||  | |||| | | ||||| ||  |||    ||||| || | | |  |||| | | ||||   |    |||   | | | |   | | | | |  ||| | || | |   | ||  ||
| ||||||  |   /+-+++-++++++-+++++--+-++++-+-+-+++++-++--+++----+++++\|| | | |  |||| | | ||||   |    |||   | | | |   | | | | |/-+++-+-++\| |   | ||  ||
| ||||||  |   || ||| |||||\-+++++--+-/||| \-+-+++++-++--+++----++++++++-+-+-+--++++-+-+-++++---+----+++---+-+-+-+---+-+-+-+-++-+++-+-++++-+---/ ||  ||
| ||||||  |   || ||| |||||  |||||  |/-+++---+-+++++-++--+++----++++++++-+-+-+--++++-+-+-++++---+----+++--\| | | |   | | | | || ||| | |||| |     ||  ||
| ||||||  |   || ||| |||||  |||||  || |||   | ||||| ||  |||    ||||||||/+-+-+--++++-+-+-++++---+\   |||  || | | |   | | | | || ||| | |||| |     ||  ||
| ||||||  |   || ||| |||||  |||||  || |||   | ||||| ||  ||| /--++++++++++-+-+--++++-+-+-++++---++---+++--++-+-+-+--\| | | | || ||| | |||| |     ||  ||
| |||||| /+---++-+++-+++++--+++++--++-+++---+-+++++-++\ ||| |  |||||||||| | |  |||| | | ||||   ||   |||  || | | |  || | | | || ||| | |||| |     ||  ||
| |||||| ||   || ||| |||||  |||||  || |||   | |||||/+++-+++-+--++++++++++-+-+--++++-+-+-++++---++\  |||  || | | |  || | | | || ||| | |||| |     ||  ||
| |||||| ||   || ||| |||||  |||||  ||/+++---+-+++++++++-+++-+--++++++++++-+-+--++++-+-+-++++---+++--+++--++-+-+-+--++-+-+-+-++-+++\| |||| |     ||  ||
| |||||| ||   || ||| |||||  |||||  ||||||   | |\+++++++-+++-+--+/|||||||| | |  |||| | | ||||   |||  |||  || | | |  || | | | || ||||| |||| |     ||  ||
| |||||| ||   || ||| |||||  |||||  ||||||   \-+-+++++++-+++-+--+-++++++++-+-+--++++-+-+-++++---+++--+++--++-+-+-+--++-/ | | ||/+++++-++++\|     ||  ||
| |\++++-++---++-+++-+++++--+++++--++++++-----+-+++++++-+++-+--+-++++++++-+-+--++/| | | ||||   |||  |||  || | | |  ||   | | |||||||| ||||||     ||  ||
| | ||||/++---++-+++-+++++--+++++--++++++-----+-+++++++-+++-+--+-++++++++-+-+--++-+-+-+-++++---+++--+++\ || | | |  ||   | | |||||||| ||||||     ||  ||
| | |||||||   || ||| |||||  |||||  ||||||    /+-+++++++\||| |  | |||||||| | |  || | | | ||||   |||  |||| || | | |  ||   | | |||||||| ||||||     ||  ||
| | ||\++++---++-+++-+++++--+++++--++++++----++-+++++++++++-+--+-++++++++-+-+--++-+-+-+-/|||   |||  |||| || | | |  ||   | | |||||||| ||||||     ||  ||
| | || |||| /-++-+++-+++++--+++++--++++++----++-+++++++++++-+--+-++++++++-+-+--++-+-+-+--+++---+++--++++-++-+-+-+\ ||   | | |||||||| ||||||     ||  ||
| \-++-++++-+-++-+++-+++++--+++++--++++++----++-+++++++++/| |/-+-++++++++-+-+--++-+-+-+--+++---+++--++++-++-+-+-++-++---+-+-++++++++\||||||     ||  ||
|   || |||| | || ||| \++++--+++++--++++++----++-+++++++++-+-++-+-++++++++-+-+--++-+-+-+--+++---+++--++++-++-+-+-++-++---+-+-++++/||||||||||     ||  ||
|   || \+++-+-++-+++--++++--/||||  |||||| /--++-+++++++++-+-++-+-++++++++-+-+--++-+-+-+--+++---+++--++++-++-+-+-++-++--\| | |||| ||||||||||     ||  ||
|   ||  ||| | || |||  ||||   ||||  |||||| |  || ||||||||| | || | |||||||| | |  || | | |  |||/--+++--++++-++\| | || ||  || | |||| ||||||||||     ||  ||
|   ||  ||| | || |||  ||\+---++++--++++++-+--++-+++++++++-+-++-+-+/|||||| | | /++-+-+-+--++++--+++--++++-++++-+-++-++--++-+-++++-++++++++++-\   ||  ||
|   ||  ||| | || |||  \+-+---++++--/||||| |/-++-+++++++++-+-++-+-+-++++++-+-+-+++-+-+-+--++++--+++\ |||| |||| |/++-++--++-+-++++-++++++++++-+\  ||  ||
|   ||  ||| | || |||   | |   ||||   ||||| || || ||||||||| | || | | \+++++-+-+-+++-+-+-+--++++--++++-++++-++++-++/| ||  || | |||| |||||||||| ||  ||  ||
|   ||  ||| | || |||   | |   ||||   ||||| || || ||||||||| | || | |  ||||| | | ||| | | |  ||||  |||| |||| |||| || | ||  || | |||| |||||||||| ||  ||  ||
|   ||  ||| | || |||   | |   ||||   |||\+-++-++-+++++++++-+-++-+-+--+++++-+-+-+++-+-/ |  ||||  |||| |||| |||| || | ||  || | |||| |||||||||| ||  ||  ||
|   \+--+++-+-++-/||   \-+---++++---+++-+-++-++-+++++++++-+-++-+-+--+++++-+-+-+++-+---+--++++--++++-++++-++++-++-+-++--++-+-/||| |||||||||| ||  ||  ||
|    |  ||| | ||  ||     |   ||||   ||| | || ||/+++++++++-+-++-+-+--+++++-+-+-+++-+---+\ ||||/-++++-++++-++++-++-+-++--++-+-\||| |||||||||| ||  ||  ||
|    |  ||| | ||  ||     |   ||||/--+++-+-++-++++++++++++-+-++-+\|  ||||| | | ||| |   || ||||| |||| |||| |||| || | ||  ||/+-++++-++++++++++-++--++-\||
|    |  ||| | ||  ||     |   |||||  ||| | || |||||||||||| | || ||\--+++++-+-+-+++-+---++-++/|| |||| |||| |||| || | ||  |||\-++++-+++++++/|| ||  || |||
|    |  ||| | ||  ||     |   ||||| /+++-+-++-++++++++++++-+-++-++---+++++-+-+-+++-+---++-++-++-++++-++++-++++\|| | ||  |||  |||| |||v||| || ||  || |||
|    |  ||| | ||  ||     |   |||\+-++++-+-++-++++++++++++-+-++-++---+++++-+-/ ||| |   || || || |||| |||| ||||||| | ||  |||  |||| ||||||| || ||  || |||
|    |  ||| | ||  ||     |   ||| | |\++-+-++-++++++++++++-+-++-++---+++++-+---+++-+---++-++-++-++++-++++-/|||||| | ||  |||  |||| ||||||| || ||  || |||
|    |  ||| | ||  ||     |   ||| | | || | || |||||||||||| | || ||   ||||| \---+++-+---++-++-++-++++-++++--++++++-+-++--+++--++++-+++++/| || ||  || |||
|    |  ||| | ||  ||     |   ||| | | || | || |||||||||||| | || ||   |||||     ||| |   || || || \+++-++++--++++++-+-++--+++--++++-+++++-+-++-++--++-++/
|    |  ||| | ||  ||     |   ||| | | \+-+-++-++++++++++++-+-++-++---+++++-----+++-+---++-++-++--+++-++++--++++++-+-++--+++--++++-+/||| | || ||  || || 
|    \--+++-+-++--++-----+---+++-+-+--+-+-++-+++++++/|||| | || ||   |||||     ||| |   || || ||  ||| ||||  |||||| | ||  |||  |||| | ||| | || ||  || || 
|       ||| | ||  ||     |   |\+-+-+--+-+-++-+++++++-++++-+-++-++---+++++-----+++-+---++-++-++--+++-++/|  |||||| | ||  |||  |||| | ||| | || ||  || || 
|       ||| | ||  ||   /-+---+-+-+-+--+-+-++-+++++++-++++-+-++-++---+++++-----+++-+---++-++-++--+++-++-+--++++++-+-++--+++--++++\| ||| | || ||  || || 
|       ||| | ||  ||   |/+---+-+-+-+--+-+-++-+++++++-++++-+-++-++\  |||||    /+++-+---++-++-++--+++-++-+-\|||||| | ||  |||  |||||| |v| | || ||  || || 
|       ||| |/++--++---+++---+-+-+-+--+-+\|| ||\++++-++++-+-++-+++--+++++----++++-+---+/ \+-++--+++-++-+-+++/||| | ||  |||  |||||| ||| | || ||  || || 
|       ||| ||||  ||   |||   | | | |  | |||| || |||| |||| | || |||  |||||    |||| |   |   | ||  ||| || | ||| ||| | ||  |||  |||||| ||| | || ||  || || 
|       ||| ||||  ||/--+++---+-+-+-+\ | |||| || |||| |||| | || |||  |||||    |||| |   |   | ||  ||| || | ||| ||| | ||  |||  |||||| ||| | || ||  || || 
|       ||| ||||  |||  |||   | | | || | |||| || |||| \+++-+-++-+++--+++++----++++-+---+---+-++--+++-++-+-+++-+++-+-++--+++--+++++/ ||| | || ||  || || 
|   /---+++-++++--+++\ |||   | | | || | |||| || ||||  ||| | || |||  ||\++----++++-+---+---/ ||  |||/++-+-+++-+++-+-++>-+++--+++++-\||| | || ||  || || 
|   |   ||| ||||  |||| ||\---+-+-+-++-+-++++-++-++++--+++-+-++-+++--++-++----+++/ |   |     ||  ||||||/+-+++-+++-+-++--+++-\||||| |||| | || ||  || || 
|   |   ||| |||\--++++-++----+-/ | || | |||\-++-++++--+++-+-++-+++--++-++----+++--+-->+-----++--++/||||| ||| ||| | ||  ||| |||||| |||| | || ||  || || 
|   |   ||| |||   |||| ||    |   | || | |||  || ||||  ||| | || |||  || ||    |||  |   |     ||  || ||||| ||| ||| | ||  ||| |||||| |||| | || ||  || || 
|   |   ||| |||   |||| |\----+---+-++-+-+++--++-++++--+++-+-++-++/  || ||    |||  |   |     ||  || ||||| ||| ||| | ||  ||| |||||| |||| | || ||  || || 
|   |   ||| |||   |||| |     |   | \+-+-+++--++-++++--+++-+-++-++---++-++----+++--+---+-----++--++-+++++-+++-/|| | ||  ||| |||||| |||| | || ||  || || 
|   |   ||| |||   |||| |   /-+---+--+-+-+++--++-++++--+++-+-++-++---++-++----+++--+---+-----++--++\|||||/+++--++-+-++--+++-++++++-++++-+-++-++-\|| || 
|   |   ||| |||  /++++-+---+-+---+\ | | |||  || ||||  ||| | || ||   || ||    |||  |   |     ||  ||||||||||||  || | ||  ||| |||||| |||| | || || ||| || 
|   |   ||| |||  ||||| |   | |   || | | |||  || ||||  ||| | || ||   || ||    |\+--+---+-----++--++++++++++++--++-+-++--+++-++++++-++++-+-++-/| ||| || 
|   |   \++-+++--+++++-+---+-+---++-+-+-+++--++-++++--+++-+-++-++---++-++----+-+--+---+-----++--+++++++/||||  || | ||  ||| |||||| |||| | ||  | ||| || 
|   |    || |||  ||||| |   | |   || | | |||/-++-++++--+++-+-++-++---++-++----+-+--+---+-----++--+++++++-++++--++-+-++--+++-++++++-++++-+-++--+-+++-++\
|   |    || |||  ||||| |   |/+---++-+-+-++++-++-++++--+++-+-++-++---++-++----+-+--+---+-----++--+++++++-++++--++-+-++-\||| |||||| |||| | ||  | ||| |||
|   |    || |||  ||||| |   |||   || | | |||| || ||||  ||| \-++-++---+/ ||    | |  |   |     ||  ||||||| ||||  || | || |||| |||||| |||| | ||  | ||| |||
|   |    || |||  ||||| |   |||   || | | |||| |\-++++--++/   || ||   |  ||    | \--+---+-----++--+++++++-++++--++-+-++-++++-++++++-++++-+-++--+-+/| |||
|   |    || |||  ||||| |   |||   || | | |||| |  ||||  || /--++-++---+--++\   |    |   |     ||  ||||||| ||||  || | |\-++++-++++++-++++-+-++--+-+-/ |||
|   |    || |||  ||||| |   |||   || | | \+++-+--++++--++-+--++-++---+--+++---+----+---+-----++--+++++++-++++--/| | |  |||| |||||| |||| | ||  | |   |||
|   |    || |||  ||||| |   |||   || | |  ||| |  |\++--++-+--++-/|   |  \++---+----+---+-----++--/|||||| ||||   | | |  |||| |||||| |||| | ||  | |   |||
|   |    || |||  ||\++-+---+++---++-+-+--+++-+--+-++--++-+--++--+---+---++---+----+---+-----++---++++/| ||||   | | |  |||| |||||| |||| | ||  | |   |||
|   |    || |||  || || |   |||   || | |  ||| |  | ||  || |  ||  |   |   ||   |    |   |     ||   |||| | ||||   | | |  |||| |||||| |||| | ||  | |   |||
|   |    || |||  || || |   |||   || | |  ||| |  | |\--++-+--++--+---+---++---+----+---+-----++---/||| | ||||   | | |  |||| |||||| ||v| | ||  | |   |||
|   |    || |||  || || |   |||   || | |  ||| |  | |   ||/+--++--+---+---++---+----+---+-----++----+++-+-++++\  | | |  |||| |||||| |||| | ||  | |   |||
\---+----++-+++--++-++-+---+++---++-+-/  ||| |  | |   ||||  ||  |   |   ||   |    |   |     ||    ||| | |||||  \-+-+--++++-++++++-++++-+-++--/ |   |||
    |    || |||  || || |   |||   \+-+----+++-+--+-+---++++--++--/   |   ||   |    |   |     ||    ||| | |||||    | |  |||| |||||| |||| | ||    |   |||
    |    || |\+--++-++-+---+++----+-+----/|| |  | |   ||||  ||      |   ||   |    |   \-----++----+++-+-+++++----+-+--++++-++++++-+/|| | ||    |   |||
    |    || | |  || || |   |||    | |     || |  | |   ||||  ||      |   ||   |    |         ||    ||| | |||||    | |  |||| |||||| | || | |\----+---+/|
    |    || | |  ||/++-+---+++-\  | |   /-++-+--+-+---++++-\||      |   ||   |    |         ||    ||| | |||||    | |  |||\-++++++-+-++-+-+-----+---/ |
    \----++-+-+--++++/ |   ||| |  | |   | || |  | |   |||| |||      |   ||   |    |         ||    ||\-+-+++++----+-+--++/  |||||| | || | |     |     |
         || | |  ||||  |   ||| |  | |   | || |  | |   |||| |||/-----+--\||   |    \---------++----++--+-+++++----+-+--++---++++++-+-+/ | |     |     |
         || | |  ||||  |   ||| |  | |   | \+-+--+-+---++++-++++-----+--+++---+--------------++----++--+-+++++----+-+--+/   |||||| | |  | |     |     |
         || | |  ||||  |   ||| |  | |   |  | |  \-+---++++-++++-----+--+++---+--------------++----++--+-+++++----+-+--+----++++/| | |  | |     |     |
         || | |  ||||  |   ||| |  | |   |  | |    |   ||\+-++++-----+--+++---+--------------++----++--+-++++/    | |  |    ||\+-+-+-+--/ |     |     |
         |\-+-+--++++--+---+++-+--+-+---+--+-+----+---++-+-++++-----+--+/|   |              ||    |\--+-++++>----+-+--+----++-+-+-/ |    |     |     |
   /-----+--+-+\ ||||  |   ||| |  | |   |  | |    |   || | ||||     |  | |   |              ||    |   | ||||     | |  |    || | |   |    |     |     |
   |     |  | || ||||  |   ||| |  |/+---+--+-+----+---++-+\||||     |  | |   |              ||    |   | \+++-----+-+--+----++-+-+---+----+-----/     |
   |     |  | || ||v\--+---+++-+--++/   \--+-+----+---++-++/|||     |  | |   |              ||    |   |  |||     | |  |    || | |   |    |           |
   |     |  | || |||   |   |\+-+--++-------+-+----+---++-++-+++-----+--+-+---+--------------++----+---+--+++-----+-+--/    || | |   |    |           |
   |     |  | || |||   |   | | |  ||       | |    |   || || |||     |  | |   |              ||    |   |  |||     | |       || | |   |    |           |
   |     |  | || |||   |   | | |  ||       | |    |   || || |||     |  | |   |              ||    |   ^  |||     | |       || | |   |    |           |
   |     |  | || |||   |   | | |  ||       | \----+---+/ || \++-----+--+-+---+--------------++----+---+--+++-----+-/       || | |   |    |           |
   |     |  | || |\+---+---+-+-+--++-------+------+---+--++--++-----+--+-+---+--------------++----+---+--+/|     |         || | |   |    |           |
   |     |  | \+-+-+---+---+<+-+--++-------+------+---+--++--++-----/  | |   |              |\----+---+--+-+-----+---------+/ | |   |    |           |
   |     |  |  | | |   |   | | |  ||       |      |   |  ||  |\--------/ |   |              |     |   |  | |     |         |  | |   |    |           |
   |     |  |  | | |   |   | | |  ||       \------+---+--++--+-----------+---+--------------+-----+---+--+-+-----+---------+--+-+---+----+-----------/
   |     |  |  | | |   |   | | |  |\--------------+---+--+/  |           |   |              |     |   |  | |     |         |  | |   |    |            
   |     |  |  | | |   |   | | |  |               |   |  |   |           |   |              |     |   |  | |     |         |  | |   |    |            
   |     |  |  | | |   |   \-+-+--+----->---------+---+--+---+-----------+---+--------------+-----/   |  | |     |         |  | |   |    |            
   |     \--+--+-+-+---+-----+-+--+---------------+---/  |   |           |   |              |         |  | |     |         |  | |   |    |            
   \--------+--/ | |   |     | |  |               |      |   |           |   |              |         |  | |     |         |  \-+---+----/            
            \----+-+---+-----+-+--+---------------+------+---+-----------+---+--------------+---------+--+-+-----/         |    |   |                 
                 \-+---+-----+-+--/               |      |   |           |   |              |         \--+-+---------------/    |   |                 
                   |   |     | |                  |      |   |           |   \--------------+------------/ |                    |   |                 
                   |   |     \-+------------------/      |   |           |                  |              |                    |   |                 
                   \---+-------/                         |   \-----------+------------------+--------------+--------------------+---/                 
                       \-----------------------<---------+---------------+------------------+--------------+--------------------/                     
                                                         \---------------/                  \--------------/                                          

I'm aware I use a bit more horizontal whitespace than normal. I find it easier to parse. Sorry if that's jarring.

I'm new to the language so suggestions on a more idiomatic style would be appreciated. I'm fairly sure there's something I should do differently around initialization of the track layout. I'm also a bit unsatisfied with the way it's continuously replacing the map. Fortunately, I don't have to manage the resources myself and I can see memory usage stays flat, but I can't help wonder if there isn't a better way.

Answer 1

Your code is quite good, but could be more concise.

Specifically, I don't see why you would need all those classes and enums: a track, for instance, is adequately represented by the same char that is used for displaying it. Carts are only a bit more complicated, since you have to remember which direction it chose last, but a std::pair<char, char> is quite enough. Besides, actual chars are more expressive than enums, for instance:

char change_direction(char current) {
    switch (current) {
        case '<': return '^';
        case '^': return '>';
        case '>': return '<';
        default: throw bad_direction();
    }
}

'x' can be used to represent a crash.

It is also very simple to keep track of each track and cart position by maintaining two arrays representing the grid on which they are positioned.

So two std::arrays are enough to represent all your data. The tick function can have the signature std::vector<int> tick(const std::array<char, N>& tracks, std::array<std::pair<char, char>, N>& carts): it lets all carts advance once and returns a vector of the crashes that occurred during the turn.

You then have a really simple loop as your program:

constexpr std::array<char, N> tracks { /* input */ };
std::array<char, N> carts { /* input */ };
constexpr auto is_cart = [](char c) { c != ' '; };
int nb_carts = std::count_if(carts.begin(), carts.end(), is_cart);

int first_crash_location = -1;
int last_cart_location = -1;
while (true) {
    std::vector<int> crashes = tick(tracks, carts);
    if (first_crash_location == -1 && !crashes.empty())
        first_crash_location == *crashes.begin();
    nb_carts -= crashes.size();
    if (nb_carts == 1) {
        last_cart_location = std::distance(carts.begin(), 
                                 std::find_if(carts.begin(), carts.end(), is_cart));
        break;
}

That leaves only the tick function to be implemented. The only tedious thing is to iterate over the array of carts in the good order (row by row, beginning with the last row), but the general idea is:

for each cell of cart_array in the good order:
    if there is a cart:
        position = compute_next_position(cart)
        clear cell
        if occupied(position, cart_array): add crash to result, clear position
        else: cart_array[position] = new_direction_cart(cart, position, track_array)