Determine which pairs of lines intersect within a given area, in the future.
Toggle the code
# path is one line of the original inputget_line <-function(path) { nums <- aochelpers::extract_numbers(path) px <- nums[1] py <- nums[2] vx <- nums[4] vy <- nums[5] m <- vy/vx b <- py - m * pxreturn(list(px = px, py = py, m = m, b = b, vx = vx, vy = vy))}both_in_range <-function(x, y, min =200000000000000, max =400000000000000) {ifelse(x >= min && x <= max && y >= min && y <= max,TRUE,FALSE)} paths_intersect <-function(path1, path2) { A <-get_line(path1) B <-get_line(path2)# parallel lines won't intersectif (A$m == B$m) {# print("lines are parallel")return(FALSE) }# point of intersection x <- (B$b - A$b)/(A$m - B$m) y <- A$m * x + A$b# check if in pastif (x > A$px && A$vx <0|| x < A$px && A$vx >0) {#print("intersect in past for A")return(FALSE) }if (x > B$px && B$vx <0|| x < B$px && B$vx >0) {#print("intersect in past for B")return(FALSE) }both_in_range(x, y)}# check all pairs# need stringsAsFactors = FALSE to enable comparison to get unique pairsall_pairs <-expand.grid(input, input, stringsAsFactors =FALSE)unique_pairs <- all_pairs[all_pairs$Var1 < all_pairs$Var2, ]mapply(paths_intersect, unique_pairs$Var1, unique_pairs$Var2) |>sum()
[1] 24192
Now that there have been a few puzzles in which we need to extract all the numbers from a string, I’ve added a function, extract_numbers() to my aochelpers package to do that, which comes in handy today.
A bit of maths gets us the equation of a line and, for any pair of lines, their point of intersection. Then, it’s just a case of checking whether they intersected in the past (the part of the puzzle that caught me out for a bit) and, if not, whether they intersect in the test area.
Finally we use expand.grid() to get all pairs of lines, then filter down to unique pairs. We can then apply our paths_intersect() function to all unique pairs, using mapply() since paths_intersect() takes more than one argument. Since TRUE has a numeric value of 1 and FALSE is 0, the sum of the output of paths_intersect() on all pairs gives the number of pairs of lines which intersect, as required.
Part 2
The crux of the puzzle
Find the starting position and velocity of a rock which, when thrown, will hit all the hailstones.
We need to throw a rock so that it hits all hailstones. To do this, we need to set up a system of equations and solve them to find the starting position and velocity. We also do not know the time of the various collisions, so that’s further unknowns.
I was pretty stumped on how to do this in R, so for the first time in many days, tried getting help from ChatGPT and Copilot, both of which were unable to come up with a solution. Their suggested code did not make much sense, and did not run. I’ll be reflecting more on my experiences of using LLMs to help with Advent of Code when I write my wrap-up post. (Spoiler, they weren’t a lot of help, nor fun).
As the day progressed, I saw some other solutions and blogs published on this, which made it clear that some kind of solver was required, e.g. this one in Python using z3-solver, or this one by Šimon Tóth, who turned to the online solver SageMath.
As part of my quest to learn during Advent of Code, I worked through Šimon’s solution, making sure I understood what he was doing, then adapted his SageMath code to work with my input.
For my own future self, here’s how the system works on the example input. Let \(p = (x, y, z)\) be the starting position and let \(v = (vx, vy, vz)\) be the velocity of the rock. In order to set up enough equations to be able to solve for so many unknowns, we need to consider when and where it intersects with three hailstones, which might as well be the first three in the list.
The position of the rock at time \(t\) is \(p + v*t\) (I’m being lazy here and not using vector notation). At some time, \(t_1\), it intersects with hailstone 1, which has starting position \(p_1 = (19, 13, 30)\) and starting velocity \(v_1 = (-2, 1, -2)\). We assume we don’t know \(t_1\), as we won’t for the actual input. At the point of intersection, we have \(p + v*t_1\) = \(p_1 + v_1*t_1\). We can break this down for each co-ordinate, to get three equations:
\(x + vx*t_1\) = \(x_1 + vx_1*t_1\)
\(y + vy*t_1\) = \(y_1 + vy_1*t_1\)
\(z + vz*t_1\) = \(z_1 + vz_1*t_1\)
Substituting in the known values of \(p_1\) and \(v_1\) and rearranging slightly, we get:
\(x + (vx + 2)t_1 = 19\)
\(y + (vy - 1)t_1 = 13\)
\(z + (vz + 2)t_1 = 30\)
Similarly, we then set up another three equations for the rock intersecting with hailstone 2 at time \(t_2\) and a final three equations for the rock intersecting with hailstone 3 and time \(t_3\). We then have a system of nine equations with nine unknowns, which is solveable. In SageMaths, the code looks like this:
x = var('x')
y = var('y')
z = var('z')
vx = var('vx')
vy = var('vy')
vz = var('vz')
t1 = var('t1')
t2 = var('t2')
t3 = var('t3')
eq1 = 19 == x + (vx+2)*t1
eq2 = 13 == y + (vy-1)*t1
eq3 = 30 == z + (vz+2)*t1
eq4 = 18 == x + (vx+1)*t2
eq5 = 19 == y + (vy+1)*t2
eq6 = 22 == z + (vz+2)*t2
eq7 = 20 == x + (vx+2)*t3
eq8 = 25 == y + (vy+2)*t3
eq9 = 34 == z + (vz+4)*t3
solutions = solve([eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9],x,y,z,vx,vy,vz,t1,t2,t3)
solutions[0][0]+solutions[0][1]+solutions[0][2]
This gives an output of x + y + z == 47, as per the example. Substituting in the values of the first three hailstones in my actual input gives the sum as 664822352550558.
It was a shame not to be able to figure out how to do this in R, but I’m glad to now know about SageMath and wonder if it may come in handy in the future.
Session info
Toggle
─ Session info ───────────────────────────────────────────────────────────────
setting value
version R version 4.3.2 (2023-10-31)
os macOS Sonoma 14.1
system aarch64, darwin20
ui X11
language (EN)
collate en_US.UTF-8
ctype en_US.UTF-8
tz Europe/London
date 2023-12-24
pandoc 3.1.1 @ /Applications/RStudio.app/Contents/Resources/app/quarto/bin/tools/ (via rmarkdown)
quarto 1.4.526 @ /usr/local/bin/quarto
─ Packages ───────────────────────────────────────────────────────────────────
package * version date (UTC) lib source
aochelpers * 0.1.0.9000 2023-12-24 [1] local
sessioninfo * 1.2.2 2021-12-06 [1] CRAN (R 4.3.0)
[1] /Users/ellakaye/Library/R/arm64/4.3/library
[2] /Library/Frameworks/R.framework/Versions/4.3-arm64/Resources/library
──────────────────────────────────────────────────────────────────────────────
Source Code
---title: "2023: Day 24"date: 2023-12-24author: - name: Ella Kayecategories: [base R, aochelpers, system of equations, SageMath, ⭐⭐]draft: false---## Setup[The original challenge](https://adventofcode.com/2023/day/24)[My data](input){target="_blank"}## Part 1```{r}#| echo: falseOK <-"2023"<3000# Will only evaluate next code block if an actual year has been substituted for the placeholder.``````{r}#| eval: !expr OKlibrary(aochelpers)input <-aoc_input_vector(24, 2023)head(input)```::: {.callout-note collapse="false" icon="false"}## The crux of the puzzleDetermine which pairs of lines intersect within a given area, in the future.:::```{r}#| cache: true# path is one line of the original inputget_line <-function(path) { nums <- aochelpers::extract_numbers(path) px <- nums[1] py <- nums[2] vx <- nums[4] vy <- nums[5] m <- vy/vx b <- py - m * pxreturn(list(px = px, py = py, m = m, b = b, vx = vx, vy = vy))}both_in_range <-function(x, y, min =200000000000000, max =400000000000000) {ifelse(x >= min && x <= max && y >= min && y <= max,TRUE,FALSE)} paths_intersect <-function(path1, path2) { A <-get_line(path1) B <-get_line(path2)# parallel lines won't intersectif (A$m == B$m) {# print("lines are parallel")return(FALSE) }# point of intersection x <- (B$b - A$b)/(A$m - B$m) y <- A$m * x + A$b# check if in pastif (x > A$px && A$vx <0|| x < A$px && A$vx >0) {#print("intersect in past for A")return(FALSE) }if (x > B$px && B$vx <0|| x < B$px && B$vx >0) {#print("intersect in past for B")return(FALSE) }both_in_range(x, y)}# check all pairs# need stringsAsFactors = FALSE to enable comparison to get unique pairsall_pairs <-expand.grid(input, input, stringsAsFactors =FALSE)unique_pairs <- all_pairs[all_pairs$Var1 < all_pairs$Var2, ]mapply(paths_intersect, unique_pairs$Var1, unique_pairs$Var2) |>sum()```Now that there have been a few puzzles in which we need to extract all the numbers from a string, I've added a function, `extract_numbers()` to my [**aochelpers**](https://ellakaye.github.io/aochelpers) package to do that,which comes in handy today.A bit of maths gets us the equation of a line and, for any pair of lines, their point of intersection. Then, it's just a case of checking whether they intersected in the past (the part of the puzzle that caught me out for a bit) and, if not, whether they intersect in the test area.Finally we use `expand.grid()` to get all pairs of lines, then filter down to unique pairs.We can then apply our `paths_intersect()` function to all unique pairs, using `mapply()` since `paths_intersect()` takes more than one argument. Since `TRUE` has a numeric value of `1` and `FALSE` is `0`, the sum of the output of `paths_intersect()` on all pairs gives the number of pairs of lines which intersect, as required.## Part 2::: {.callout-note collapse="false" icon="false"}## The crux of the puzzleFind the starting position and velocity of a rock which,when thrown, will hit all the hailstones.:::We need to throw a rock so that it hits all hailstones.To do this, we need to set up a system of equations and solve them to find the starting position and velocity. We also do not know the time of the various collisions, so that's further unknowns.I was pretty stumped on how to do this in R,so for the first time in many days, tried getting help from ChatGPT and Copilot, both of which were unable to come up with a solution.Their suggested code did not make much sense, and did not run.I'll be reflecting more on my experiences of using LLMs to help with Advent of Code when I write my wrap-up post. (Spoiler, they weren't a lot of help, nor fun).As the day progressed, I saw some other solutions and blogs published on this, which made it clear that some kind of solver was required, e.g. [this one in Python using z3-solver](https://github.com/nharrer/AdventOfCode/blob/main/2023/day24/solve_day24.py), or [this one](https://simontoth.substack.com/p/daily-bite-of-c-advent-of-code-day-31a?r=1g4l8a&utm_campaign=post&utm_medium=web) by Šimon Tóth, who turned to the online solver [SageMath](https://cocalc.com/features/sage?utm_source=sagemath.org&utm_medium=landingpage). As part of my quest to learn during Advent of Code, I worked through Šimon's solution, making sure I understood what he was doing, then adapted his [SageMath code](https://cocalc.com/share/public_paths/745575e6352019a1ab86955d641ad6b3eacca4c8) to work with my input.For my own future self, here's how the system works on the example input. Let $p = (x, y, z)$ be the starting position and let $v = (vx, vy, vz)$ be the velocity of the rock. In order to set up enough equations to be able to solve for so many unknowns, we need to consider when and where it intersects with three hailstones, which might as well be the first three in the list.The position of the rock at time $t$ is $p + v*t$ (I'm being lazy here and not using vector notation). At some time, $t_1$, it intersects with hailstone 1, which has starting position $p_1 = (19, 13, 30)$ and starting velocity $v_1 = (-2, 1, -2)$. We assume we don't know $t_1$, as we won't for the actual input. At the point of intersection, we have $p + v*t_1$ = $p_1 + v_1*t_1$. We can break this down for each co-ordinate, to get three equations:$x + vx*t_1$ = $x_1 + vx_1*t_1$$y + vy*t_1$ = $y_1 + vy_1*t_1$$z + vz*t_1$ = $z_1 + vz_1*t_1$Substituting in the known values of $p_1$ and $v_1$ and rearranging slightly, we get:$x + (vx + 2)t_1 = 19$$y + (vy - 1)t_1 = 13$$z + (vz + 2)t_1 = 30$Similarly, we then set up another three equations for the rock intersecting with hailstone 2 at time $t_2$ and a final three equations for the rock intersecting with hailstone 3 and time $t_3$. We then have a system of nine equations with nine unknowns, which is solveable. In SageMaths, the code looks like this:```x = var('x')y = var('y')z = var('z')vx = var('vx')vy = var('vy')vz = var('vz')t1 = var('t1')t2 = var('t2')t3 = var('t3')eq1 = 19 == x + (vx+2)*t1eq2 = 13 == y + (vy-1)*t1eq3 = 30 == z + (vz+2)*t1eq4 = 18 == x + (vx+1)*t2eq5 = 19 == y + (vy+1)*t2eq6 = 22 == z + (vz+2)*t2eq7 = 20 == x + (vx+2)*t3eq8 = 25 == y + (vy+2)*t3eq9 = 34 == z + (vz+4)*t3solutions = solve([eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9],x,y,z,vx,vy,vz,t1,t2,t3)solutions[0][0]+solutions[0][1]+solutions[0][2]```This gives an output of `x + y + z == 47`, as per the example.Substituting in the values of the first three hailstones in my actual input gives the sum as `664822352550558`.It was a shame not to be able to figure out how to do this in R, but I'm glad to now know about SageMath and wonder if it may come in handy in the future.##### Session info {.appendix}<details><summary>Toggle</summary>```{r}#| echo: falselibrary(sessioninfo)# save the session info as an objectpkg_session <-session_info(pkgs ="attached")# get the quarto versionquarto_version <-system("quarto --version", intern =TRUE)# inject the quarto infopkg_session$platform$quarto <-paste(system("quarto --version", intern =TRUE), "@", quarto::quarto_path() )# print it outpkg_session```</details>