https://adventofcode.com/2021/day/20
For day 20, our puzzle was to use "image enhancement" on a "map"
obtained by our sensor/beacon arrangement.
Our email system is going to wrap lines here, so keep in mind that
there's only a single line before the blank line in this data sample:
sample=:{{)n
..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
#..#.
#....
##..#
..#..
..###
}}
You might prefer to pull the sample data from the original puzzle page...
Anyways, that first line in the sample represents our "image
enhancement algorithm", and the subsequent lines represent the image
which we need to enhance.
In both cases, we're converting to binary. The "image enhancement
algorithm" is a 512 bit vector, which means that it provides a 1 bit
value which can be selected by a nine bit index.
The image enhancement algorithm is: take a 3 by 3 tile centered on the
bit being enhanced, convert those nine bits to an integer, and use
that to look up the result bit in the algorithm specification from the
first line of our data.
So... to parse the data, I had
use=: {{
lines=. <@('.#'&i.);._2 y -.' '
assert. 512-:#0{::lines
(0{::lines);>2}.lines
}}
And, conveniently, this lookup mechanism worked here:
lookup=:{{
(#.,y){x
}}
In tacit form that would be
lookup=: {~ #.@,
(I said "conveniently" because it might have been that I would have
needed to arrange the bits in some different order, perhaps a reverse
order, perhaps reversing rows and/or columns, perhaps transposing the
bits from the tile. So it's really nice that none of that was
necessary.)
But the critical part of this puzzle is to tile the "image", look up
each of the new bits for the image (and then repeat that process as
many times as necessary). J's tessellation conjunction -- something
like (1,:3 3) F;._3 Y -- is almost what we need here. But it needs
padding on all sides so that every original bit gets a 3 by 3 tile.
Also, because of you u;._3 works, this leaves us a bit of garbage at
the end which needs to be trimmed off (these correspond to the right
hand side and the bottom row, where u;._3 would give us 2 by 3 or 3 by
2 or in one case a 2 by 2 tile).
Conceptually, our "image" was part of an infinite grid of bits where
the bits outside of our image started out being all zeros.
In other words:
pad=:{{
sh=.$y
fill=. (<0 0){y
(-4+sh){.!.fill(2+sh){.!.fill y
}}
enh=: {{
_2 _2}.(1,:3 3) x&lookup;.3 pad y
}}
There's a trick here in the 'pad' verb. To make this work
consistently, I slightly altered my 'use' verb:
use=: {{
lines=. <@('.#'&i.);._2 y -.' '
assert. 512-:#0{::lines
(0{::lines);0,>}.lines
}}
This adds two rows of padding (zeros) to the top of the 'image'. (One
row from the '0,' part of the phrase, the other because replacing
'2}.' with a simple '}.' includes the blank line from the data as an
image row.)
Note that, conceptually, a single row of padding would have been
sufficient. If a single row was not sufficient, the image would have
been growing significantly faster than it was observed to grow -- we
would have needed two rows and two columns of padding on all sides for
that type of image enhancement algorithm.
For the sample data, it was sufficient to use 0 for all padding. For
our actual puzzle input we had a different image enhancement algorithm
which alternated between needing 1s for padding and needing 0s for
padding. (The first item in that 512 bit vector was 1 and the last
item was 0.)
Experimentally, my original 'use' (without the initial padding lines)
worked just fine for my input data, but for the general case, I wanted
to be sure that I was considering all possibilities (even though I
wasn't). Anyways... for now I'll stick with my two rows of padding.
(It's quite all right to hard code the implementation to include
details from the puzzle data, but doing that makes the code more
difficult to explain. Here, I could have split this up into odd step
and even step and used 1 for padding on the second (or even) steps and
0 for padding on the first (or odd) steps. But that approach would not
work on the sample data. (But I could have made a copy of the sample
data and glued in the image enhancement algorithm from my puzzle
input.))
The actual puzzle was to run this image enhancement step n time (2 for
part A, 50 for part B) and count the number of lit pixels in the
resulting image.
a20=:{{
'alg scan'=. use y
+/,alg enh^:2 scan
}}
b20=:{{
'alg scan'=. use y
+/,alg enh^:50 scan
}}
Mind you... these images did not carry any meaning for me when I looked at them.
look=:{{
require'viewmat'
'alg scan'=. use y
viewmat 2}.alg enh^:x scan
}}
FYI,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
