--- Day 8: Resonant Collinearity ---
You find yourselves on the roof of a top-secret Easter Bunny installation.
While The Historians do their thing, you take a look at the familiar huge antenna. Much to your surprise, it seems to have been reconfigured to emit a signal that makes people 0.1% more likely to buy Easter Bunny brand Imitation Mediocre Chocolate as a Christmas gift! Unthinkable!
Scanning across the city, you find that there are actually many such antennas. Each antenna is tuned to a specific frequency indicated by a single lowercase letter, uppercase letter, or digit. You create a map (your puzzle input) of these antennas. For example:
............ ........0... .....0...... .......0.... ....0....... ......A..... ............ ............ ........A... .........A.. ............ ............The signal only applies its nefarious effect at specific antinodes based on the resonant frequencies of the antennas. In particular, an antinode occurs at any point that is perfectly in line with two antennas of the same frequency - but only when one of the antennas is twice as far away as the other. This means that for any pair of antennas with the same frequency, there are two antinodes, one on either side of them.
So, for these two antennas with frequency
a, they create the two antinodes marked with#:.......... ...#...... .......... ....a..... .......... .....a.... .......... ......#... .......... ..........Adding a third antenna with the same frequency creates several more antinodes. It would ideally add four antinodes, but two are off the right side of the map, so instead it adds only two:
.......... ...#...... #......... ....a..... ........a. .....a.... ..#....... ......#... .......... ..........Antennas with different frequencies don't create antinodes;
Aandacount as different frequencies. However, antinodes can occur at locations that contain antennas. In this diagram, the lone antenna with frequency capitalAcreates no antinodes but has a lowercase-a-frequency antinode at its location:.......... ...#...... #......... ....a..... ........a. .....a.... ..#....... ......A... .......... ..........The first example has antennas with two different frequencies, so the antinodes they create look like this, plus an antinode overlapping the topmost
A-frequency antenna:......#....# ...#....0... ....#0....#. ..#....0.... ....0....#.. .#....A..... ...#........ #......#.... ........A... .........A.. ..........#. ..........#.Because the topmost
A-frequency antenna overlaps with a0-frequency antinode, there are14total unique locations that contain an antinode within the bounds of the map.Calculate the impact of the signal. How many unique locations within the bounds of the map contain an antinode?
g: read0 `8.txt; n: count g
Now, we want to find the indices of all values other than "."
Let's start by defining all indices.
show idx:i cross i: til n 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 ..
We can then use these indices with group.
idx group raze g .| (0 0;0 1;0 2;0 3;0 4;0 5;0 6;0 7;0 8;0 9;0 10;0 11;1 0;1 1;1 2;1 3;1 4;1 5.. 0| (1 8;2 5;3 7;4 4) A| (5 6;8 8;9 9)So drop ".", and take the values.
show ant: value "." _ idx group raze g TODONow, we need to iterate over pairs of indices. Let's write a helper function that generates pairs.
0N!{x (;)/:\: x} (1 2;3 4;5 6)
(((1 2;1 2);(1 2;3 4);(1 2;5 6));((3 4;1 2);(3 4;3 4);(3 4;5 6));((5 6;1 2);(..
1 2 1 2 1 2 3 4 1 2 5 6
3 4 1 2 3 4 3 4 3 4 5 6
5 6 1 2 5 6 3 4 5 6 5 6
The 0N! is used to display it in the k format, rather than in Q's formatted version, which here isn't very helpful.
We can see we have the pairs, but we don't want to count the same one twice, and don't want to have both (x;y) and (y;x).
So we drop 1 2 3... from each row. We then use raze to merge the lists.
0N!{raze (1+til count x) _' x (;)/:\: x} (1 2;3 4;5 6)
((1 2;3 4);(1 2;5 6);(3 4;5 6))
1 2 3 4
1 2 5 6
3 4 5 6
Save this to a function.
pairs:{raze (1+til count x) _' x (;)/:\: x}
Now, given two positions, we want to generate the two values of "antinodes".
If we have two values, x and y, we can find the difference d.
Then the two "antinode" values will be at (x-d; y+d).
gen:{d:y-x; (x-d; y+d)}.
The use of Apply (.) here is so that it can take an argument as (p1; p2).
Now we can find all antinodes.
gen each' pairs each ant ((0 11;3 2);(-1 9;5 6);(-2 12;7 0);(1 3;4 9);(0 6;6 3);(2 10;5 1)) ((2 4;11 10);(1 3;13 12);(7 7;10 10))We need to raze this twice to flatten it into a list of positions, and save the values. I'm using a view here so that node will automatically update if other variables do.
node::2 raze/gen each' pairs each antWe can display our nodes on the grid. First find the suitable ones, by indexing. If it returns a null value, we're out of bounds.
node where not null g ./: node 0 11 3 2 5 6 7 0 1 3 4 9 0 6 6 3 2 10 5 1 2 4 11 10 1 3 7 7 10 10Now amend g with "#" at these positions. Again, I'm saving the variable disp as a view.
disp::g .[;;:;"#"]/ node where not null g ./: nodeWe can print this to stdout by applying the file handle 1 to it.
-1@disp; ......#....# ...#....0... ....#0....#. ..#....0.... ....0....#.. .#....#..... ...#........ #......#.... ........A... .........A.. ..........#. ..........#.And our result is the number of hashes in disp.
ans::sum "#"=raze disp
show ans 14i
--- Part Two ---
Watching over your shoulder as you work, one of The Historians asks if you took the effects of resonant harmonics into your calculations.
Whoops!
After updating your model, it turns out that an antinode occurs at any grid position exactly in line with at least two antennas of the same frequency, regardless of distance. This means that some of the new antinodes will occur at the position of each antenna (unless that antenna is the only one of its frequency).
So, these three
T-frequency antennas now create many antinodes:T....#.... ...T...... .T....#... .........# ..#....... .......... ...#...... .......... ....#..... ..........In fact, the three
T-frequency antennas are all exactly in line with two antennas, so they are all also antinodes! This brings the total number of antinodes in the above example to9.The original example now has
34antinodes, including the antinodes that appear on every antenna:##....#....# .#.#....0... ..#.#0....#. ..##...0.... ....0....#.. .#...#A....# ...#..#..... #....#.#.... ..#.....A... ....#....A.. .#........#. ...#......##Calculate the impact of the signal using this updated model. How many unique locations within the bounds of the map contain an antinode?
(x;y), we calculate d:y-x but now return (x-n*d; x-(n-1)*d; ...; x+n*d).
gen:{d:y-x; x+/:d*/:n - til 2*n}.
Because our values are defined using views, they update automatically.
ans 34i
g: read0 `:i/8.txt; n: count g
idx: i cross i:til n
ant: value "." _ idx group raze g
gen:{d:y-x; (x-d;y+d)}.
pairs: raze {(1+til count x) _' x(;)/:\:x} @
node::2 raze/ gen each' pairs each ant
disp::g .[;;:;"#"]/ node where not null g ./: node
ans::sum sum disp="#"
show ans / part 1
gen:{d:y-x; x+/:d*/:n - til 2*n}.
show ans / part 2