Day 8: Resonant Collinearity
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
J
J really doesn’t have hashes! Or anything like hashes! And it’s really annoying after a while!
What it does have is automatic internal optimization via hashing of the “index of” operation m i. n where m is a fixed list (the object being searched) and n is the query, which can vary. But as soon as you update m the hash table is thrown away. And you still have to choose some kind of numeric key, or store a list of boxed pairs where the first coordinate is the key – effectively this is an old-style Lisp association list, but with extra steps because you have to use boxing to defeat J’s automatic array concatenation and reshaping. If you want non-cubical shapes (J calls these “ragged arrays”), or heterogeneous lists, you end up writing u a lot – this means “unbox, apply u then rebox”. J arrays are required to be rectangular and homogeneous, but a boxed anything is a single atom just like a number is.
It’s just a really bad choice of language if you want data structures other than essentially-cubical arrays. On the other hand, once you beat the list manipulation primitives into producing your 1970s Lisp data structure of choice, the rest of the program is as nice as it usually is.
data_file_name =: '8.data'
grid =: ,. > cutopen fread data_file_name
'rsize csize' =: $ grid
inbounds =: monad : '(*/ y >: 0 0) * (*/ y < rsize, csize)'
antenna_types =: (#~ (~: & '.')) ~. , grid
NB. list_antennas gives a list of boxed matrices of shape 2 n_k in cell k, where
NB. n_k is the number of antennas of type k and the rows are coordinates of that type
list_antennas =: monad define
antenna_locs =. (# antenna_types) $ a:
for_r. i. rsize do.
for_c. i. csize do.
cell =. y {~ <(r, c)
if. '.' ~: cell do.
at =. antenna_types i. cell
antenna_locs =. ((<(r, c)) ,&.> at { antenna_locs) at} antenna_locs
end.
end.
end.
NB. _2 ]\ l reshapes l into length 2 rows without finding its length ahead of time
(_2 & (]\))&.> antenna_locs
)
NB. a1 pair_antinodes a2 gives the two antinodes from that pair
pair_antinodes =: dyad : '(#~ inbounds"1) ((2 * x) - y) ,: (2 * y) - x'
NB. if u is a symmetric dyad expecting rank 1 arguments, u on_pairs is a monad
NB. expecting a list of rank 1 arguments, and yields the concatenation of x u y
NB. where (x, y) is drawn from the (unordered) pairs of elements of the argument
NB. see page_pairs in 5.ijs for a non-point-free version of pair enumeration
on_pairs =: adverb define
; @: (< @: u/"2) @: ({~ (; @: (< @: (,~"0 i.)"0) @: i. @: #))
)
NB. antinodes antennas gives a list (may contain duplicates) of all the antinodes from
NB. that set of antennas
antinodes =: pair_antinodes on_pairs
NB. on_antennas concatenates and uniquifies result lists from all antennas
on_antennas =: adverb define
~. @: ; @: (u &.>) @: list_antennas
)
result1 =: # antinodes on_antennas grid
NB. a1 res_antinodes a2 gives the list of antinodes from that pair with resonance
res_antinodes =: dyad define
step =. (% +./) x - y
NB. lazy: max_steps doesn't take location of x into account
max_steps =. <. (rsize % 1 >. | 0 { step) <. (csize % 1 >. 1 { step)
(#~ inbounds"1) x +"1 step *"1 0 i: max_steps
)
result2 =: # res_antinodes on_pairs on_antennas grid
