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 classPos(valx:Int,valy:Int)enumclassDir{LEFT,RIGHT,UP,DOWN}enumclassTurn{LEFT,STRAIGHT,RIGHT}data classPlan(valdir:Dir,valturn:Turn)data classCart(valid:Int,valpos:Pos,valplan:Plan,valcollided:Boolean=false)typealiasTrack=ChartypealiasTracks=List<CharArray>data classModel(valtracks:Tracks,valcarts: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.
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.
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.
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.
funCart.checkCollisions(carts:Collection<Cart>):Cart=if(carts.any{c->c.collided})this// only want the first collisionelseif(carts.none{c->c.pos==pos})thiselsethis.copy(collided=true)funModel.tick():Model{valnewCarts=cartsInScanOrder.fold(carts){carts_,c->valotherCarts=carts_.filter{it!=c}otherCarts+c.move(tracks).checkCollisions(otherCarts)}returnModel(tracks,newCarts)}
Running the simulation makes use of an infinite sequence of states I call the timeline:
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.
funModel.tick():Model{valnewCarts=cartsInScanOrder.fold(carts){carts_,c->if(!carts_.contains(c))// removed by collisioncarts_else{valc_=c.move(tracks)valotherCarts=carts_.filter{it!=c}valcrash=c_.collision(otherCarts)if(crash==null)otherCarts+c_elseotherCarts.filterNot{it==crash}}}returnModel(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.
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:
Loading the input data
The input text lines are just mapped to
CharArray
s. Then I use a pair offoldIndexed()
calls run over the input on both axes and find the locations of the carts. A starting model for each cart is built here.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.
Part 1
Cart movement is broken into a bunch of little functions, each of which should be pretty easy to understand.
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.Moving a cart is a matter of determining the new plan based on the current track character, then executing the plan.
Scanning for the order to move the carts makes use of a nice Kotlin library feature of chainable comparators:
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.
Running the simulation makes use of an infinite sequence of states I call the timeline:
Just drop states from this sequence until a collision is detected, then find the crashed cart:
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.
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.