--- Day 14: Restroom Redoubt ---
One of The Historians needs to use the bathroom; fortunately, you know there's a bathroom near an unvisited location on their list, and so you're all quickly teleported directly to the lobby of Easter Bunny Headquarters.
Unfortunately, EBHQ seems to have "improved" bathroom security again after your last visit. The area outside the bathroom is swarming with robots!
To get The Historian safely to the bathroom, you'll need a way to predict where the robots will be in the future. Fortunately, they all seem to be moving on the tile floor in predictable straight lines.
You make a list (your puzzle input) of all of the robots' current positions (
p) and velocities (v), one robot per line. For example:p=0,4 v=3,-3 p=6,3 v=-1,-3 p=10,3 v=-1,2 p=2,0 v=2,-1 p=0,0 v=1,3 p=3,0 v=-2,-2 p=7,6 v=-1,-3 p=3,0 v=-1,-2 p=9,3 v=2,3 p=7,3 v=-1,2 p=2,4 v=2,-3 p=9,5 v=-3,-3Each robot's position is given as
p=x,ywherexrepresents the number of tiles the robot is from the left wall andyrepresents the number of tiles from the top wall (when viewed from above). So, a position ofp=0,0means the robot is all the way in the top-left corner.Each robot's velocity is given as
v=x,ywherexandyare given in tiles per second. Positivexmeans the robot is moving to the right, and positiveymeans the robot is moving down. So, a velocity ofv=1,-2means that each second, the robot moves1tile to the right and2tiles up.The robots outside the actual bathroom are in a space which is
101tiles wide and103tiles tall (when viewed from above). However, in this example, the robots are in a space which is only11tiles wide and7tiles tall.The robots are good at navigating over/under each other (due to a combination of springs, extendable legs, and quadcopters), so they can share the same tile and don't interact with each other. Visually, the number of robots on each tile in this example looks like this:
1.12....... ........... ........... ......11.11 1.1........ .........1. .......1...These robots have a unique feature for maximum bathroom security: they can teleport. When a robot would run into an edge of the space they're in, they instead teleport to the other side, effectively wrapping around the edges. Here is what robot
p=2,4 v=2,-3does for the first few seconds:Initial state: ........... ........... ........... ........... ..1........ ........... ........... After 1 second: ........... ....1...... ........... ........... ........... ........... ........... After 2 seconds: ........... ........... ........... ........... ........... ......1.... ........... After 3 seconds: ........... ........... ........1.. ........... ........... ........... ........... After 4 seconds: ........... ........... ........... ........... ........... ........... ..........1 After 5 seconds: ........... ........... ........... .1......... ........... ........... ...........The Historian can't wait much longer, so you don't have to simulate the robots for very long. Where will the robots be after
100seconds?In the above example, the number of robots on each tile after 100 seconds has elapsed looks like this:
......2..1. ........... 1.......... .11........ .....1..... ...12...... .1....1....To determine the safest area, count the number of robots in each quadrant after 100 seconds. Robots that are exactly in the middle (horizontally or vertically) don't count as being in any quadrant, so the only relevant robots are:
..... 2..1. ..... ..... 1.... ..... ..... ..... ...12 ..... .1... 1....In this example, the quadrants contain
1,3,4, and1robot. Multiplying these together gives a total safety factor of12.Predict the motion of the robots in your list within a space which is
101tiles wide and103tiles tall. What will the safety factor be after exactly 100 seconds have elapsed?
First of all, let's parse the input.
show (p;v):flip "J"$","vs''2_''" "vs'read0 `14.txt 0 4 6 3 10 3 2 0 0 0 3 0 7 6 3 0 9 3 7 3 2 4 9 5 3 -3 -1 -3 -1 2 2 -1 1 3 -2 -2 -1 -3 -1 -2 2 3 -1 2 2 -3 -3 -3
Now, define a variable for the grid size. For our sample input, it is 11 7 but for the real input it should be 101 103.
show dims:11 7 11 7
The coordinates after 100 seconds can be found by multiplying v by 100 and adding it to the initial position. Mod is then used to account for the wrapping.
show pos: (p + 100*v) mod\: dims 3 5 5 4 9 0 4 5 1 6 1 3 6 0 2 3 0 2 6 0 4 5 6 6
We can visualise this like so:
".12" flip (dims#0) .[;;+;1]/ pos "......2..1." "..........." "1.........." ".11........" ".....1....." "...12......" ".1....1...."
Now, we need to check which quadrant each position is in. For both the x and y values, we can use bin to assign a value between 0 and 2.
Then, we can use 3 sv to map to numbers from 0 to 8.
3 sv'' 0N!0 1 2 ,/:\: 0 1 2 ((0 0;0 1;0 2);(1 0;1 1;1 2);(2 0;2 1;2 2)) 0 1 2 3 4 5 6 7 8
show sections: 3 sv dims {(0,0 1+x div 2) bin y}' flip pos
2 5 6 2 2 1 6 1 0 6 2 8
As we want the four "corners", we count the positions corresponding to 0,2,6, and 8. We then take the product of the counts.
prd 0N!(count each group sections) 0 2 6 8 1 4 3 1 12
--- Part Two ---
During the bathroom break, someone notices that these robots seem awfully similar to ones built and used at the North Pole. If they're the same type of robots, they should have a hard-coded Easter egg: very rarely, most of the robots should arrange themselves into a picture of a Christmas tree.
What is the fewest number of seconds that must elapse for the robots to display the Easter egg?
Note: this section works best if you replace the sample input with your own input, and replace dims accordingly.
There are a couple of ways to approach this.
One is to continually output the values in the console and stop when you get an image of a christmas tree. However, the more programmatic way would be to try to detect it. This can be done a few different ways, but the easiest is probably to look for many consecutive points.
We can use sv to map 2d to 1d, and sort the positions.
asc dims sv/: pos `s#2 10 13 17 26 33 33 39 42 42 48 63
Counting adjacent ones is then counting where the difference is 1.
sum 1=0N!deltas asc dims sv/: pos 2 8 3 4 9 7 0 6 3 0 6 15 0i
We can use while to increment 1 until a sufficient number of adjacent values appear.
The if statement is to stop it running until dims has been redefined, to prevent infinite loops.
if[dims~101 103; t:{100>sum 1=deltas asc dims sv/: (p+x*v)mod\:dims} {1+x}/ 1]
t
't
[0] t
^
We can visualise the result:
-1@flip (dims#"") .[;;:;"X"]/ (p+t*v)mod\:dims;
X
X X X
X
X
X X
X
X X X X X
X X
X X
X
X X
X X X
X X
X X
X X X
X X
X X
X X X
X
X X X
X X
X X
X
X
X X
X X
X
X
X X
X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X
X X X X
X X X
X X
X X
X X X
X XXX X X
X X X XXXXX X
X XXXXXXX X X X
X XXXXXXXXX X X X X X
X XXXXX X X X
X X XXXXXXX X X
X XXXXXXXXX X X
X XXXXXXXXXXX X
X XXXXXXXXXXXXX X X
X XXXXXXXXX X X
X XXXXXXXXXXX X
X XXXXXXXXXXXXX X
X XXXXXXXXXXXXXXX X
X XXXXXXXXXXXXXXXXX X
X XXXXXXXXXXXXX X
X XXXXXXXXXXXXXXX X X X
X X XXXXXXXXXXXXXXXXX X X
X XXXXXXXXXXXXXXXXXXX X X
X XXXXXXXXXXXXXXXXXXXXX X X
X XXX X
X XXX X X X
X X X XXX X
X X
X X X X
X X X X
X X X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X
X X X
X
X X
XX X
X X X X
X X
X X
X X
X X
X X
X
X X X
X X
X
X X
X X
X X
X X
X X X
X
X
X
X X
X X
X X
X X
X X
(p;v):flip "J"$","vs''2_''" "vs'read0 `:i/14.txt
dims: 101 103
pos: (p + 100*v) mod\: dims
sections: 3 sv dims {(0,0 1+x div 2) bin y}' flip pos
prd (count each group sections) 0 2 6 8
{100>sum 1=deltas asc dims sv/: (p+x*v)mod\:dims} {1+x}/ 135+101k and 12+103k.
The intersection of these then gives my result of 6398.
k:til 100; (35+101*k) inter (12+103*k) ,6398